3
$\begingroup$

If not, is there a decision procedure that successfully classifies any polynomial time algorithm as poly-time within a time polynomially bounded by the length of the input algorithm?

$\endgroup$
5
$\begingroup$

Here is an example. Suppose that you're working within axiom system A, say ZFC. Gödel showed that if A is consistent then A can't prove that A is consistent. Consider the following program:

On input $x$, go over all strings of length $\log |x|$, and check if one of them is a proof of the consistency of A. If so, loop for $2^{|x|}$ iterations. Otherwise, halt.

This is polynomial time if and only if A is consistent. If A could prove that this algorithm terminates in polynomial time then A has just proved that A is consistent, which is impossible if A is indeed consistent. Yet if we believe that A is consistent, then the machine does run polynomial time; but A unfortunately isn't strong enough to prove it.

Your second question asks whether there is an algorithm that, given a Turing machine $T$, answers in polynomial time whether $T$ is a polynomial time Turing machine. Unfortunately, this is undecidable. Suppose that we only consider Turing machines which don't depend on their input (say the first thing they do is erase their input). Such a machine $T$ runs is polynomial time if and only if it halts on the empty tape. Deciding whether a Turing machine halts is impossible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.