DocumentCode
1992702
Title
Some consequences of our failure to prove non-linear lower bounds on explicit functions
Author
Lipton, Richard J.
Author_Institution
Dept. of Comput. Sci., Princeton Univ., NJ, USA
fYear
1994
fDate
28 Jun- 1 Jul 1994
Firstpage
79
Lastpage
87
Abstract
Investigates the consequences of assuming that no explicit function has non-polynomial size Boolean circuit complexity. There are many consequences of this assumption. For example, it immediately proves that P does not equal NP. It also has ramifications for the length of certain interactive proofs
Keywords
Boolean functions; computational complexity; NP complexity class; explicit functions; interactive proof lengths; nonlinear lower bounds; nonpolynomial size Boolean circuit complexity; Arithmetic; Boolean functions; Circuits; Complexity theory; Computer science; Mathematics; Turing machines;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
Conference_Location
Amsterdam
Print_ISBN
0-8186-5670-0
Type
conf
DOI
10.1109/SCT.1994.315815
Filename
315815
Link To Document