# What's the error about the definition of NP?

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?

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.

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."