Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ALMOST OPTIMAL ALGORITHM:
Reports tagged with almost optimal algorithm:
TR11-085 | 14th May 2011
Yijia Chen, Joerg Flum, Moritz Müller

Hard instances of algorithms and proof systems

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

ISSN 1433-8092 | Imprint