Title :
A note on the instance complexity of pseudorandom sets
Author_Institution :
Dept. of Comput. Sci., State Univ. of New York, Stony Brook, NY, USA
Abstract :
The relationship between the notion of pseudorandomness and the notion of hard instances is investigated. It is proved that if A is random (or pseudorandom), then most instances to A are hard instances (or, respectively, have nontrivial instance complexity). These results are used to show that if one-way functions that are secure against polynomial-size circuits exist, then an NP-hard problem A must have a nonsparse core of which all instances have nontrivial instance complexity
Keywords :
computability; computational complexity; NP-hard; hard instances; instance complexity; nontrivial instance complexity; polynomial-size circuits; pseudorandom sets; pseudorandomness; random sets; Algorithm design and analysis; Circuits; Complexity theory; Computer science; Cryptography; Polynomials; Turing machines;
Conference_Titel :
Structure in Complexity Theory Conference, 1992., Proceedings of the Seventh Annual
Conference_Location :
Boston, MA
Print_ISBN :
0-8186-2955-X
DOI :
10.1109/SCT.1992.215407
