Improving on Gutfreund, Shaltiel,and Ta-Shma’s Paper “If NP Languages Are Hard on the Worst-Case, Then It Is Easy to Find Their Hard Instances”

DOI10.1007/978-3-642-38536-0_18zbMath1381.68093OpenAlexW175851554MaRDI QIDQ4928485

Nikolai K. Vereshchagin

Publication date: 14 June 2013

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-38536-0_18

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

A remark on pseudo proof systems and hard instances of the satisfiability problem