0
$\begingroup$

Many sources (including Wolfram's MathWorld) say that NP problem is defined as a decision problem "verifiable in nondeterministic polynomial time" (check Google to see more sources).

But accordingly Wikipedia tells that NP are problems that can be solved in non-determnistic polynomial time.

From conjunction of these two statements it follows that $\mathrm{P}=\mathrm{NP}$, because any algorithm verifies itself.

So, apparently MathWorld and many others are wrong in their definition of NP? Or what do I misunderstand?

If "verifiable in nondeterministic polynomial time", is not a definition of NP, then how is it indeed called?

$\endgroup$
3
$\begingroup$

If a problem $A$ is verifiable in polynomial-time by a non-deterministic Turing machine $T$ (given an instance of the problem and certificate of length polynomially bounded in the size of the instance) then it is also solvable in polynomial-time by a non-deterministic Turing machine $T'$.

The Turing machine $T'$ simply (non-deterministically) guesses the certificate (among all certificates having a polynomially-bounded length) and then (non-deterministically) checks whether each certificate candidate is valid using $T$.

This shows that $A \in \mathsf{NP}$.

Conversely, if a problem is in $\mathsf{NP}$ then it is verifiable in polynomial-time by a deterministic Turing machine $T$. Clearly, $T$ is also a non-deterministic Turing machine.

$\endgroup$
1
$\begingroup$

The class $\mathsf{NP}$ can be defined either as

  1. the class of languages that can be verified by a deterministic polynomial time algorithm;

  2. the class of languages that can be solved by a nondeterministic polynomial time algorithm.

Regarding 1), a verification algorithm is a two-argument algorithm $A$, where one argument is an ordinary input string $x$, and the other argument is a binary string $y$ called a certificate. The algorithm $A$ verifies $x$ if there exists a $y$ such that $A(x,y)=1$. The language verified by a verification algorithm A is $L=\{ x \in \{0,1\}^* |$ there exists $y \in \{0,1\}^*$ such that $A(x,y)=1$.

Regarding 2), defining

$\operatorname{NTIME}_{\operatorname{TM}}(T(n)) = \{R: \exists$ a nondeterministic Turing Machine with time complexity $O(T(n))$ on any computation path that accepts $R\}$

then $\mathsf{NP} = \operatorname{NTIME}_{\operatorname{TM}}(n^{O(1)})$

Regarding Wolfram's MathWorld, it is worth noting here that the same web site (see their definition of NP-Problem) reports that "A problem is assigned to the $\mathsf{NP}$ (nondeterministic polynomial time) class if it is solvable in polynomial time by a nondeterministic Turing machine."

$\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.