August 2017 – nivotko

${\bf NP}$ is the class of languages that can be decided in polynomial time by a non-deterministic Turing Machine. Now let ${\bf NP}'$ be the class of languages that can be recognized in polynomial time by a non-deterministic Turing machine.

We can ask the same question: Is ${\bf NP}={\bf NP}'$ ?

Theorem. ${\bf NP}={\bf NP}'$ .

The proof is almost the same, except that we use non-deterministic Turing Machine, instead of deterministic one. For completeness of the detail, I will write the proof.

Proof. Clearly, ${\bf NP} \subseteq {\bf NP}'$ . Now, let $L \in {\bf NP}'$ . Then there exists a non-deterministic Turing Machine that will accept $x \in L$ in $p(n)$ time, for some polynomial $p$ . Now, we construct a non-deterministic Turing Machine $M'$ that will decide $L$ in polynomial time. Let $M'$ on input $x$ runs a simulation of $M(x)$ in $p(n)$ time. If it halts and ACCEPT, then $M'$ also accepts. Otherwise, REJECT. $\square$

Still, the proof is non-constructive.

Let ${\bf P}$ be a class of languages that can be decided in polynomial time by a deterministic Turing Machine. Let ${\bf P}'$ be a class of languages that can be accepted (recognized) in polynomial time by a deterministic Turing Machine.

Theorem. ${\bf P}={\bf P}'$ .

This theorem appears in CLRS book. The proof is non-constructive, roughly as follows.

Proof. It is true that ${\bf P} \subseteq {\bf P}'$ because if it can be decided, then it can be recognized. To prove ${\bf P}' \subseteq {\bf P}$ , let $L \in {\bf P}'$ . Because it can be recognized in polynomial time, then there is a polynomial $p(n)$ such that $L$ can be recognized by a Turing Machine $M$ in $p(n)$ time for input $x$ of length $|x|=n$ . We now construct a polynomial-time deterministic Turing Machine $M'$ that decides $L$ . Let $M'$ is a Turing Machine with input $x$ simulates $M(x)$ up to $p(n)$ time. If it halts and ACCEPT, then $M'$ also ACCEPT. Otherwise, simply REJECT. $\square$

The main idea of the proof is that if an input $x$ is in $L$ , then the Turing Machine $M$ must have definitive answer before the $p(n)$ -th step. If not, then we are sure that $x$ is not an element of $L$ .

The non-constructive part of the proof is when the proof uses polynomial bound $p(n)$ . The only thing that is given is the fact that $L \in {\bf P}$ , and the question is how can we find a polynomial bound for $L$ ? Is there a constructive method to find such polynomial $p$ ?

Month: August 2017

Non-deterministic version of accepting and deciding

Non-constructive proof in complexity