Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR11-085 | 14th May 2011 07:54

#### Hard instances of algorithms and proof systems

TR11-085
Authors: Yijia Chen, Joerg Flum, Moritz Müller
Publication: 30th May 2011 13:27
Keywords:

Abstract:

Assuming 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.

ISSN 1433-8092 | Imprint