Hard Instances of Algorithms and Proof Systems
Yijia Chen, Jörg Flum, Moritz Müller · ACM Transactions on Computation Theory · 2014
If the class TAUT of tautologies of propositional logic has no almost optimal algorithm, then every algorithm A deciding TAUT has a hard sequence, that is, a polynomial time computable sequence witnessing that A is not almost optimal. We show that this result extends to every Π t p -complete problem with t ≥1; however, assuming the Measure Hypothesis, there is a problem which has no almost optimal algorithm but is decided by an algorithm without hard sequences. For problems Q with an almost optimal algorithm, we analyze whether every algorithm deciding Q , which is not almost optimal, has a hard sequence.