# Confusion related to the definition of NP problems

I have this confusion related to the definition of NP problems. According to wikipedia

Intuitively, NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes". More precisely, these proofs have to be verifiable in polynomial time by a deterministic Turing machine. In an equivalent formal definition, NP is the set of decision problems where the "yes"-instances can be accepted in polynomial time by a non-deterministic Turing machine.

However, as far as I know NP is the set of problems which cannot be solved in polynomial time, but given a solution it can be verified in polynomial time. Now from the definition of wikipedia, I think the part where it says that they have verifiable proofs means the part that the solution can be verified in polynomial time. But I didn't get the first part where it says NP is the set of decision problems where the "yes"-instances can be accepted in polynomial time by a non-deterministic Turing machine. (Does this mean that the problem cannot be solved in polynomial time, even if it could it is by non deterministic turing machine rather than the deterministic one?).

Further I was referring to a book where it says

The input to a computational problem will be encoded as a finite binary string s. We denote the length of a string s by |s|. We will identify a decision problem X with the set of strings on which the answer is “yes.” An algorithm A for a decision problem receives an input string s and returns the value “yes” or “no”—we will denote this returned value by A(s). We say that A solves the problem X if for all strings s, we have A(s)=yesif and only if s∈X.

Now, how should we formalize the idea that a solution to a problem can be checked efficiently, independently of whether it can be solved efficiently? A “checking algorithm” for a problem X has a different structure from an algorithm that actually seeks to solve the problem; in order to “check” a solution, we need the input string s, as well as a separate “certificate” string t that contains the evidence that s is a “yes” instance of X.

The above definition from the book are hard to grasp. Can any provide some intuition?

-
As a short note: your 'as far as I know' is wrong. NP is, simply (and simplifiedly), the set of decision problems for which a purported solution (that is, a 'yes' answer) can be verified in polynomial time. The 'cannot be solved in polynomial time' you add is the crux of the P=NP? question; nobody knows for certain whether every problem in NP can in fact be solved in polynomial time or not. – Steven Stadnicki May 3 '13 at 3:33
It is common to mis-read "NP" to mean "not polynomial," but that is a misreading. It officially stood for "non-deterministic polynomial," which intuitively has the meaning you quote at the beginning. So Steven is correct, your "as far as I know" is wrong. – Thomas Andrews May 3 '13 at 3:40
In fact, many problems in NP can be solved in polynomial time. If P≠NP then “most difficult” problems in NP — that are called NP-hard problems — cannot be solved in polynomial time (this is NOT a definition of NP hard problems). – Yury May 3 '13 at 3:46

## 1 Answer

This is a frequent source of confusion among people seeing NP for the first time. Let's see what the two definitions mean in the context of the Hamiltonian Circuit problem.

HAMILTONIAN CIRCUIT: Given a description of a graph $G$ (perhaps by an adjacency matrix), is there a simple circuit in $G$ that contains all vertices of $G$?

Definition 1 (verifying a solution by a deterministic computation in polynomial time). If someone claimed to have found a solution for a particular graph $G$), what would it take for us to determine whether it was indeed a solution? We could require that they present us with a certificate we could check, which in this example might be the adjacency matrix, $A$, of $G$ along with the proposed cycle, namely

$$(A, \langle\;v_1, v_2, \dots, v_n, v_1\;\rangle)$$ We'd then write a program for our (Model I, deterministic) computer take this certificate as input and verify (1) that the edges $\{v_1, v_2\}, \{v_2, v_3\}, \dots, \{v_n, v_1\}$ were edges of $G$, (2) that none of the edges were listed twice, (3) that each vertex of $G$ was contained in the cycle and (4) that no vertex appeared more than once in the cycle. It is clear that we could write such a program and that the time required by this program would be polynomial in the size, in bits, of the certificate, so HAMILTONIAN CIRCUIT is an NP problem by this definition.

Definition 2 (generating a solution using non-determinism) Suppose we just purchased a Model II nondeterministic computer which has the ability to select at each step a finite collection of statements to execute. Think of such a machine as executing all of the statements in the collection at the same time in parallel universes. Notice that in each universe our machine appears to be just a Model I deterministic machine. Trying our new computer on HAMILTON CIRCUIT, we'll instruct it to generate possible solutions by starting at a vertex $v$ and simultaneously adding all vertices adjacent to $v$ (in parallel universes). Repeating this process $n$ times, we'll end this phase with lots of parallel universes, perhaps as many as $n^n$, and in each we'll have generated a possible solution. However, in each of the universes, we'll have done just $n$ steps.

Now in each universe, we'll test whether the path we generated was a solution (answer "yes") or not (answer "no"), using the poly-time verifier we made for Definition 1. Finally our Model II computer enters God Mode: it looks at the results in all of the parallel universes and answers "yes" if and only if there was a "yes" answer in any of the parallel universes. In summary, our Model II computer can solve any instance of HAMILTON CIRCUIT in polynomial time.

This is at the heart of essentially all problems in NP: in simple terms, we nondeterministically guess a solution and then verify our guess in poly time.

Remarks

• Note that any problem that can be solved in deterministic poly time (i.e., problems in P) can be solved in nondeterministic poly time (just don't use the universe-creation feature of the Model II machine), so P $\subseteq$ NP.
• In our example, we used nondeterminism to find a poly-time solution to HAMILTONIAN CIRCUIT. That doesn't imply that there isn't a poly-time deterministic solution. Perhaps we just weren't clever enough to find one.
• At present there are no known problems in NP that have been proven not to be in P. In other words, we don't know if NP $\setminus$ P is empty or not. Equivalently, we just don't know whether P=NP or not. The consensus among many theorists is the current machinery just isn't powerful enough to settle this question so we'll have to wait until someone creates some new mathematics.
-