Unsatisfying proof for NP-Problems 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?

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.
