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
fDate :
28 Jun- 1 Jul 1994
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;
Conference_Titel :
Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
Conference_Location :
Amsterdam
Print_ISBN :
0-8186-5670-0
DOI :
10.1109/SCT.1994.315815
