Hard Instances of Algorithms and Proof Systems

DOI10.1145/2601336zbMath1321.68301MaRDI QIDQ5892128

Jörg Flum, Moritz Müller, Yijia Chen

Publication date: 3 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: http://ddd.uab.cat/record/77023

zbMATH Keywords

optimal algorithms; optimal proof systems; hard sequences; measure hypothesis

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Speedup for natural problems and noncomputability
• Almost every set in exponential time is P-bi-immune
• Observations on measure and lowness for \(\Delta_ 2^ p\)
• Optimal proof systems imply complete sets for promise classes
• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• If NP languages are hard on the worst-case, then it is easy to find their hard instances
• ON OPTIMAL INVERTERS
• Do there exist complete sets for promise classes?
• On p-Optimal Proof Systems and Logics for PTIME
• Completeness, Approximation and Density
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Results on resource-bounded measure