If NP languages are hard on the worst-case, then it is easy to find their hard instances

DOI10.1007/s00037-007-0235-8zbMath1133.68352OpenAlexW2163083173WikidataQ62398467 ScholiaQ62398467MaRDI QIDQ2475580

Ronen Shaltiel, Amnon Ta-Shma, Dan Gutfreund

Publication date: 11 March 2008

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-007-0235-8

zbMATH Keywords

Average-case complexityworst-case to average-case reductionsfoundations of cryptographypseudo classes

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ A remark on pseudo proof systems and hard instances of the satisfiability problem ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Unnamed Item ⋮ Hard Instances of Algorithms and Proof Systems ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ Circuit lower bounds from NP-hardness of MCSP under turing reductions

This page was built for publication: If NP languages are hard on the worst-case, then it is easy to find their hard instances