2
$\begingroup$

One common strategy to prove that a problem or language $L$ is NP is to show that there exists a certificate $c$ which can be verified in polynomial time by a (deterministic) Turing machine.

Let $\Sigma$ be an alphabet and $L \subset \Sigma^*$ a language. Then $L$ is in NP iff there exists a language $L' := \{x\#c \mid x \in L, c \in \{0,1\}^{p(|x|)}\}$ in P, where $|x|$ is the length of $x$ and $p$ is some polynomial, such that $x \in L$ iff $x\#c \in L'$ for some $c$.


For example to prove that HAMILTON-CYCLE is in NP, we can encode the edges of a Hamilton cycle in binary and use that as a certificate (and append as many $0$'s as needed to achieve polynomial length). Many proofs say now that it is trivial to check the solution / verify the certificate in polynomial time. That might be true in graph theory ($\mathcal O(|E(G)|)$), but not at all obvious using Turing machines.

Another example: SATISFIABILITY is in NP, since we can take any interpretation of the variables which satisfy the boolean formula. Many proofs say now that it is trivial to check the solution / verify the certificate in polynomial time (see even Wikipedia). How do you even insert the interpretation into the formula in polynomial time on a Turing machine? The head of the machine must move to the first bit of the certificate, than move back and insert it at the right position, etc.??

The problem arises since Turing machines are way more fundamental. Whereas addition and multiplication is commonly assumed to be $\mathcal O(1)$, on Turing machines, they are $\mathcal O(\log n)$ or $\mathcal O((\log n)^2)$ for numbers $n$.

So: How do you actually verify a certificate in polynomial time on a Turing machine?

$\endgroup$
2
  • 1
    $\begingroup$ The distinction between $O(1)$ and $O(\log^2 n)$ is meaningless when all one cares about is whether something runs in polynomial time or not. $\endgroup$ Commented Jan 23, 2023 at 17:53
  • $\begingroup$ @CarlSchildkraut I know, that was an example for addition. But what about any polynomial graph algorithm? $\endgroup$
    – Gargantuar
    Commented Jan 23, 2023 at 17:54

1 Answer 1

1
$\begingroup$

in general it's relatively hard to encode a solution on a Turing machine that imposes more than cubic overhead. as long as you can encode each graph theory primitive in polynomial time, the entire algorithm will be in P.

$\endgroup$
2
  • $\begingroup$ I know that if you can implement every $\mathcal O(1)$ operation in graph theory (delete an edge, advance in a list, etc.) in polynomial time on a Turing machine, then every polynomial algorithm in a graph theoretical sense is also polynomial on a Turing machine. But why doesn't anyone mention this? And how do you prove that? $\endgroup$
    – Gargantuar
    Commented Jan 24, 2023 at 8:50
  • $\begingroup$ the key points are that a polynomial algorithm has a polynomial number of steps, and the product of two polynomials is polynomial $\endgroup$ Commented Jan 24, 2023 at 17:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .