Confusion related to the definition of NP problems

Question

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?

Answer 1

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.

Answer 2

As others already mentioned, NP does not mean the problem is not solvable in polynomial time (if that were true we would have P$\neq$NP, which is unproven). As you yourself said, NP just means solvable in polynomial time by a non-deterministic Turing machine, or equivalently that the solutions are verifiable in polynomial time.

For intuition consider bin packing, which is in NP. I give you a list of $n$ numbers between $0$ and $1$ and $k$ bins, each with capacity $1$. The question is, if I can pack the elements into the bins, such that no bin overflows. Now it appears to be very hard to determine if this is possible for such an instance, as the number of possibilities of distributing $n$ elements onto $k$ beens grows exponentially. An algorithm solving this decision problem in polynomial time, would proof P=NP.

On the other side, it is very easy to verify a solution. If I give you a mapping $f:\{1,\dotsc, n\} \to \{1,\dotsc, k\}$ you can check whether or not the bin packing works, simply by applying the function to your values and check if any bin overflows at the end.

The point is that it is very easy to verify whether a map and a list of numbers and bins is an acceptable bin packing, but it seems to be very hard to for a list of numbers and bins to decide, whether or not such an accepting map $f$ exists.

To make a really simple analogy, if I give you a height, it is very hard to check if there exists a building which is taller. If I give you a height and a building, it is very easy to verify, whether or not that building is taller or shorter.