Title :
The history of complexity
Author_Institution :
NEC Res. Inst., Princeton, NJ, USA
fDate :
6/24/1905 12:00:00 AM
Abstract :
Summary form only given. We describe several trends in the history of computational complexity, including: the early history of complexity; the development of NP-completeness and the structure of complexity classes; how randomness, parallelism and quantum mechanics has forced us to reexamine our notions of efficient computation and how computational complexity has responded to these new models; the meteoric rise and fall of circuit complexity; and the marriage of complexity and cryptography and how research on a cryptographic model led to limitations of approximation
Keywords :
computational complexity; cryptography; history; NP-completeness; circuit complexity; complexity classes; computational complexity history; cryptography; parallelism; quantum mechanics; randomness; Books; Computational complexity; Computational modeling; Cryptography; History; Iron; Logic; National electric code; Parallel processing; Quantum computing;
Conference_Titel :
Computational Complexity, 2002. Proceedings. 17th IEEE Annual Conference on
Conference_Location :
Montreal, Que.
Print_ISBN :
0-7695-1468-5
DOI :
10.1109/CCC.2002.1004340