DocumentCode :
3379884
Title :
If NP languages are hard on the worst-case then it is easy to find their hard instances
Author :
Gutfreund, Dan ; Shaltiel, Ronen ; Ta-Shma, Amnon
Author_Institution :
Sch. of Comput. Sci. & Eng., Hebrew Univ. of Jerusalem, Israel
fYear :
2005
fDate :
11-15 June 2005
Firstpage :
243
Lastpage :
257
Abstract :
We prove that if NP
Keywords :
Boolean functions; computability; computational complexity; formal languages; statistical distributions; Boolean formula; NP-complete language; OWF; SAT; cryptography; polynomially samplable distribution; probabilistic polynomial time algorithm; quasipolynomial time; satisfiability; worst-case hard language; Computational complexity; Computer science; Cryptography; Information technology; NP-complete problem; Polynomials; Scholarships; Stress; Time measurement;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on
ISSN :
1093-0159
Print_ISBN :
0-7695-2364-1
Type :
conf
DOI :
10.1109/CCC.2005.11
Filename :
1443090
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=3379884
بازگشت