DocumentCode
3152409
Title
A note on the instance complexity of pseudorandom sets
Author
Ko, Ker I.
Author_Institution
Dept. of Comput. Sci., State Univ. of New York, Stony Brook, NY, USA
fYear
1992
fDate
22-25 Jun 1992
Firstpage
327
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1992., Proceedings of the Seventh Annual
Conference_Location
Boston, MA
Print_ISBN
0-8186-2955-X
Type
conf
DOI
10.1109/SCT.1992.215407
Filename
215407
Link To Document