ECCC-Report TR11-085https://eccc.weizmann.ac.il/report/2011/085Comments and Revisions published for TR11-085en-usMon, 30 May 2011 13:27:39 +0300
Paper TR11-085
| Hard instances of algorithms and proof systems |
Yijia Chen,
Joerg Flum,
Moritz MÃ¼ller
https://eccc.weizmann.ac.il/report/2011/085Assuming that the class TAUT of tautologies of propositional logic has no almost optimal algorithm, we show that every algorithm $\mathbb A$ deciding TAUT has a polynomial time computable sequence witnessing that $\mathbb A$ is not almost optimal. The result extends to every $\Pi_t^p$-complete problem with $t\ge 1$; however, we show that assuming the Measure Hypothesis there is a problem which has no almost optimal algorithm but has an algorithm without hard sequences.Mon, 30 May 2011 13:27:39 +0300https://eccc.weizmann.ac.il/report/2011/085