Title :
The shrinkage exponent is 2
Author_Institution :
R. Inst. of Technol., Stockholm, Sweden
Abstract :
We prove that if we hit a formula of size L with a random restriction from Rp then the expected remaining size is at most O(p2(log p)3/2L). As a corollary we obtain a R(n3-O(1)) formula size lower bound for an explicit function in NP
Keywords :
computational complexity; NP; explicit function; random restriction; shrinkage exponent; Computational modeling; Inspection; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on
Conference_Location :
Palo Alto, CA
Print_ISBN :
0-8186-4370-6
DOI :
10.1109/SFCS.1993.366876
