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