In basic terms, what is the definition of P, NP, NP-Complete, and NP-Hard?

Question

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that np is a subset of np complete which is a subset of np hard... but I have no idea what they actually mean. Wikipedia isn't much help either as the explanations are still a bit too high level.

Answer 1

I think the Wikipedia articles $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{P}$ vs. $\mathsf{NP}$ are quite good. Still here is what I would say:

---

Decision Problems

There are various kinds of computational problems. However in an introduction to computational complexity theory course it is easier to focus on decision problem, i.e. problems where the answer is either YES or NO. There are other kinds of computational problems but most of the time questions about them can be reduced to similar questions about decision problems. Moreover decision problems are very simple. Therefore in an introduction to computational complexity theory course we focus our attention to the study of decision problems.

We can identify a decision problem with the subset of inputs that have answer YES. This simplifies notation and allows us to write $x\in Q$ in place of $Q(x)=YES$ and $x \notin Q$ in place of $Q(x)=NO$.

Another perspective is that we are talking about membership queries in a set. Here is an example:

Decision Problem:

Input: a natural number $x$,
Question: is $x$ an even number?

Membership Problem:

Input: a natural number $x$,
Question: is $x$ in $Even = \{0,2,4,6,\cdots\}$?

We sometime refer to the YES answer for an input as accepting the input and to the NO answer on an input as rejecting the input.

---

$\mathsf{P}$ = Problems with Efficient Algorithms for Finding Solutions

Assume that efficient algorithms means algorithms that uses at most polynomial amount of computational resources. The main resource we care about is worst-case running-time of algorithms, i.e. the number of steps an algorithm takes on an input of size $n$ (size of an input is $n$ if it takes $n$-bits of computer memory to store it). So by efficient algorithms we mean an algorithms that have polynomial worst-case running-time. The assumption that polynomial-time algorithms capture the intuition notion of efficient algorithms is known as Cobham thesis.

I won't get into the arguments about if $\mathsf{P}$ really captures what can be done efficiently in practice and related issues. There are good reasons to make this assumption so for our purpose we assume this is the case. If you don't accept Cobham thesis it doesn't make what I wrote below incorrect, they only thing we will loose is the intuition about efficient computation in practice. I think it is a helpful assumption for someone who is starting to learn about complexity theory.

$\mathsf{P}$ is the class of decision problems that can be solved efficiently,
i.e. decision problems which have polynomial-time algorithms.

More formally, we say a decision problem $Q$ is in $\mathsf{P}$ iff

there is an efficient algorithm $A$ s.t.
for all inputs $x$,
* if $Q(x)=YES$ then $A(x)=YES$,
* if $Q(x)=NO$ then $A(x)=NO$.

I can simply write $A(x)=Q(x)$ but I write it this way so we can compare it to the definition of $\mathsf{NP}$.

---

$\mathsf{NP}$ = Problems with Efficient Algorithms for Verifying Certificates/Proofs/Witnesses

Sometimes we don't know any efficient way of finding the answer to a question, however if someone tells us the answer and gives us a proof we can verify that the answer is correct by checking the correctness of the proof.

However if the proof is too long it is not really useful, it can take too long to read the proof let alone check if it is correct. We want the running-time to reasonable in the size of the original input, not the proof. That means what we really want is not arbitrary long proofs but short proofs. Note that if the verifier's running-time is polynomial in the size of the original input then it can only read a polynomial part of the proof. So by short we mean polynomial size.

Form this point on whenever I use the word "proof" I mean "short proof".

Here is an example of a problem which we don't know how to solve efficiently but we can efficiently verify proofs:

Partition
Input: a finite set of natural numbers $S$,
Question: is it possible to partition $S$ into two sets $A$ and $B$ ($A \cup B = S$ and $A \cap B = \emptyset$) such that
the sum of the numbers in $A$ is equal to the sum of number in $B$ ($\sum_{x\in A}x=\sum_{x\in B}x$)?

$$ $$

If I give you $S$ and ask you if we can partition them into two sets such that their sums are equal, you don't know any efficient algorithm to solve it. You will probably try all possible ways of partitioning the numbers into two sets until you find a partition where the sums are equal or until you have tried all possible partitions and none worked. If any of them worked you would say YES, otherwise you would say NO.

But there are exponentially many possible partitions so it will probably take a lot of time. However if I give you two sets $A$ and $B$, you can easily check if the sums are equal and if $A$ and $B$ is a partition of $S$. Note that we can compute sums efficiently.

Here the pair of $A$ and $B$ that I give you is a proof for a YES answer. You can efficiently verify my claim by looking at my proof. If the answer is YES there is a proof and I can give it to you can you can verify it efficiently. If the answer is NO then there is no proof. Note that if the answer is too big it will take a lot of time to verify it, we don't want this to happen, so we only care about efficient proofs, i.e. proofs which have polynomial size. Sometimes people call these certificates in place of proofs.

I am giving you enough information about the answer for input $x$ so that you can find and verifiy the answer efficiently. For example, in our example I don't tell you the answer is YES or NO, I just give you a partition, and you can verify it. Note that you have to verify the answer yourself, you can't trust me to give you the correct answer.

Here is an example: $A=\{2,4\}$ and $B=\{1,5\}$ is a proof that $S=\{1,2,4,5\}$ can be partitioned into two sets with equal sums. We just need to sum up the numbers in $A$ and the numbers in $B$ and see if the results are equal, and check if $A$, $B$ is partition of $S$.

If I gave you $A=\{2,5\}$ and $B=\{1,4\}$, you will check and see that my proof is not correct. It doesn't mean the answer is NO, it just means that this particular proof was incorrect. Your task here is not to find the answer, but just to check if the proof you are given is correct.

It is like a student solving a question in an exam and the professor checking if the answer is correct. :) (unfortunately often students don't give enough information to verify the correctness of their answer and the professors have to guess the rest of their incomplete answer and decide how much mark they should give to the students for their partial answers, a quite difficult task).

The same situation applies to many other natural problems that we want to solve: we can efficiently verify if a given short proof is correct, but we don't know any efficient way of finding the answer. This is the motivation why the complexity class $\mathsf{NP}$ is extremely interesting (though it wasn't the original motivation for defining it). Almost whatever you do (not just in CS, but in math, biology, physics, chemistry, economics, management, sociology, ...) you will face computational problems that fall in this class.

$\mathsf{NP}$ is the class of problems which have efficient verifiers, i.e.
there is a polynomial time algorithm that can verifiy if a given answer is correct.

More formally, we say a decision problem $Q$ is in $\mathsf{NP}$ iff

there is an efficient algorithm $V$ called verifier s.t.
for all inputs $x$,

• if $Q(x)=YES$ then there is a proof $y$ s.t. $V(x,y)=YES$,
• if $Q(x)=NO$ then for all proofs $y$, $V(x,y)=NO$.

We call the property that the verifier accepts no proof for YES when the answer is NO the soundness property of the verifier. In other words, verifier cannot be tricked to answer YES if the answer is really NO.

Similarly, we call the property that verifier accepts at least one proof if the answer is YES completeness of the verifier.

The verifier $V$ gets two inputs,

• $x$ : the original input for $Q$, and
• $y$ : a suggested proof for $Q(x)=YES$.

Note that we want $V$ to be efficient in the size of $x$. If $y$ is a big proof the verifier will be able to read only a polynomial part of $y$. That is why we require the proofs to be short. If $y$ is short saying that $V$ is efficient in $x$ is the same as saying that $V$ is efficient in $x$ and $y$ (because the size of $y$ is bounded by a fixed polynomial in the size of $x$).

In summery, to show that a decision problem $Q$ is in $\mathsf{NP}$ we have to give an *efficient$ verifier which is sound and complete.

Historical Note: historically this is not the original definition of $\mathsf{NP}$. The original definition uses what is called non-deterministic machines. These machines do not correspond to any real machine model and are difficult to get used to (at least when you are starting to learn about complexity theory). I have read that many experts think that they would have used the verifier definition as the main definition and even would have named the class $\mathsf{VP}$ (for verifiable in polynomial-time) in place of $\mathsf{NP}$ if they go back to the dawn of complexity theory. The verifier definition is easier to understand and easier to use to show problems are in this class.

---

$\mathsf{P}\subseteq \mathsf{NP}$

Therefore we have $\mathsf{P}$=efficient solvable and $\mathsf{NP}$=efficiently verifiable. So $\mathsf{P}=\mathsf{NP}$ iff the problems that can be efficiently verified are the same as the problems that can be efficiently solved.

Note that any problem in $\mathsf{P}$ is also in $\mathsf{NP}$, i.e. if you can solve the problem you can also verify if a given proof is correct: we will just ignore the proof!

That is because we don't need it, we can compute the answer ourselves. If the answer is NO we know there should be no proof and our verifier will reject every suggested proof. If the answer is YES, there should be a proof, and in fact we will accept anything as a proof, independent of them we can verify that answer is YES, we don't need any information from them. (We could accept only some of them, that is also fine, as long as we accept at lest one proof the verifier works correctly for the problem).

Here is an example:

Sum
Input: a list of natural numbers $a_1,\cdot,a_n$, and $s$,
Question: is $\Sigma_{i=1}^n a_i = s$?

The problem is in $\mathsf{P}$ because we can sum up the numbers and then compare it with $s$, we return YES if they are equal, and NO if they are not.

The problem is also in $\mathsf{NP}$. Consider a verifier $V$ that gets something as a proof plus the input for Sum. It acts the same way as the algorithm in $\mathsf{P}$ that we described above. This is an efficient verifier for Sum.

Note that there are other efficient verifiers for Sum, and some of them might use the proof given to them. However the one we designed does not and that is also fine. Since we gave an efficient verifier for Sum the problem is in $\mathsf{NP}$. The same trick works for all other problems in $\mathsf{P}$ so $\mathsf{P} \subseteq \mathsf{NP}$.

---

Brute-Force/Exhaustive-Search Algorithms for $\mathsf{NP}$ and $\mathsf{NP}\subseteq \mathsf{ExpTime}$

The best algorithm we know for solving arbitrary problems in $\mathsf{NP}$ are brute-force/*exhaustive-search* algorithms, i.e. try all possible proofs and see if any of them is accepted by the verifier for the problem (it has an efficient verifier by our assumption that it is in $\mathsf{NP}$).

In our example, we try all possible partitions and check if in any of them the sums are equal.

Note that this will take exponential-time in the size of input. This shows that any $\mathsf{NP}$ problem can be solved in exponential-time, i.e. $\mathsf{NP}\subseteq \mathsf{ExpTime}$. (Moreover the brute-force algorithm will use only a polynomial amount of space and $\mathsf{NP}\subseteq \mathsf{PSpace}$ but that is a story for another time).

A problem in $\mathsf{NP}$ can have much faster algorithms, for example any problem in $\mathsf{P}$ has a polynomial-time algorithm. However for an arbitrary problem in $\mathsf{NP}$ we don't know algorithms can do much better. In other words, if you just tell me that your problem is in $\mathsf{NP}$ the fastest algorithm that we have for solving it right now will be exponential-time.

However it doesn't mean that there aren't any better algorithms, we don't know that. As far as we know it is still possible (though thought to be unlikely) that $\mathsf{NP}=\mathsf{P}$ and all $\mathsf{NP}$ problems can be solved in polynomial-time.

Some experts conjecture that we can't do much better, i.e. there are problems in $\mathsf{NP}$ that cannot be solved much more efficiently than brute-force search algorithms which take exponential amount of time (see Exponential Time Hypothesis for more information). However this is not proven, it is only a conjecture.

This association with exponential-time confuses some people: they think incorrectly that $\mathsf{NP}$ problems require exponential-time to solve (or even worse there are no algorithm for them). Stating that a problem is in $\mathsf{NP}$ doesn't mean a problem is difficult to solve, it just means that it is easy to verify, it is an upper-bound on the difficulty of solving the problem, and many $\mathsf{NP}$ problems are easy to solve since $\mathsf{P}\subseteq\mathsf{NP}$.

Never the less, there seems to be problems which seem to be hard to solve. I will return to this in when we discuss $\mathsf{NP}$-hardness.

---

Lower-Bounds Seem Difficult to Prove

OK, so we now know that there are many natural problems that are in $\mathsf{NP}$ and we don't know any efficient way of solving them and we suspect that they really require exponential-time to solve. But can we prove this?

Unfortunately the task of proving lower-bounds is very difficult. We can't even prove that these problems require more than linear time! let alone exponential-time.

(Proving linear-time lower-bounds is rather easy: the algorithm needs to read the input after all. Proving super-linear lower-bounds is a completely different story.)

To prove an upper-bound for a problem we just need to design a good enough algorithm. It often needs knowledge, creative thinking, and even ingenuity to come up with such an algorithm.

However the task is considerably simpler compared to proving a lower-bound. We have to show that there are no good algorithms. Not that we don't have any good enough algorithms right now, but that there doesn't exist any good algorithms, no one can ever come up with a good algorithm. Think about it for a minute if you haven't before, how can we show such an impossibility result?

This is another place where people get confused. Here "impossibility" is a mathematical impossibility, i.e. it is not a short coming on our part that some genius can fix in future. When we say impossible we mean it is absolutely impossible, as impossible as $1=0$. No technological advance can make it possible. That is what we are doing when we are proving lower-bounds.

To prove a lower-bound, i.e. that a problem requires some amount of time to solve means that we have to prove that any algorithm, even very ingenuous ones that don't know yet, can't solve the problem faster. There are many intelligent ideas that we know of (linear programming, matching, dynamic programming, dynamic programming, and many other intelligent ideas) and there are many many more that we don't know about. Ruling out one algorithm or one particular idea of designing algorithms is not sufficient, we need to rule out all of them, even those we don't know about. And one can combine all of these in an algorithm, so we need to rule our their combinations also. There has been some progress towards showing that some ideas cannot solve the problem but they are not even close to ruling out the intelligent ideas that we know of (search for lower-bounds in restricted models of computation if you are interested).

---

Barriers: Lower-Bounds Are Difficult to Prove

On the other hand we have mathematical results called barriers that say that a lower-bound proof cannot be such and such, and such and such almost covers all techniques that we have used to prove lower-bounds. In fact many researchers gave up working on proving lower-bounds after Razbarov and Rudich's natural proofs barrier result. It turns out that the existence of particular kind of lower-bound proofs would imply the insecurity of cryptographic pseudorandom number generators and many other cryptographic tools.

I say almost because in recent years there has been some progress mainly by Ryan Williams that has been able to intelligently circumvent the barrier results, still the results so far are for very weak models of computation and quite far from ruling out general polynomial-time algorithms.

But I am diverging. The main point I wanted to make was that proving lower-bounds is difficult and we don't have strong lower-bounds for general algorithms.

---

Reduction: Solving a Problem Using Another Problem as a Subroutine/Oracle

The idea of a reduction is very simple: to solve a problem, use an algorithm for another problem.

Here is simple example: assume we want to compute the sum of a list of $n$ natural numbers and we have an algorithm $Sum$ that return the sum of two given numbers. Can we use $Sum$ to add up the numbers in the list? Of course!

Problem:

Input: a list of $n$ natural numbers $x_1,\ldots,x_n$,
Output: return $\sum_{i=1}^{n} x_i$.

Reduction Algorithm:

1. $s = 0$
2. for $i$ from $1$ to $n$
   2.1. $s = Sum(s,x_i)$
3. return $s$

Here we are using $Sum$ in our algorithm as a subroutine. Note that we don't care about how $Sum$ works, it acts black-box for us, we don't care what is going on inside $Sum$. We often refer to the subroutine $Sum$ as oracle. It is like the oracle in Delphi, we ask questions and the oracle answers them and we use the answers.

This is essentially what a reduction is: assume that we have algorithm for a problem and use it as an oracle to solve another problem. Here efficient means efficient assuming that the oracle answers in a unit of time, i.e. we count each execution of the oracle a single step.

There are some technical details here: if the oracle returns a large answer we need to read it and that it can take some time, so we should count the time it takes us to read the answer that oracle has given to us. Similarly for writing/asking the question from the oracle. But oracle works instantly, i.e. as soon as we ask the question from the oracle the oracle writes the answer for us in a single unit of time. All the work that oracle does is counted a single step, excluding the time it takes us to write the question and read the answer.

Because we don't care how oracle works but only about the answers it returns we can make a simplification and consider the oracle to be the problem itself in place of an algorithm for it.

For example, $Sum$ in the question above is the addition function itself (not an algorithm for computing addition).

We can ask multiple questions from an oracle, and the questions doesn't need to be pre-determined: we can ask a question and based on the answer that oracle returns do some computations by yourself and then ask a new question based on the answer we got from the previous answer.

Another way of looking at this is thinking about it as an interactive computation. Interactive computation in itself is large topic so I don't get into it here, but I think mentioning this perspective of reductions can be helpful.

An algorithm $A$ that uses an oracle $O$ is usually denoted as $A^O$.

The reduction we discussed above is the most general form of a reduction and is called Turing reduction in general.

More formally:

We say that problem $Q$ is Turing reducible to problem $O$ and write $Q \leq_T O$ iff
there is an algorithm $A$ such that for all inputs $x$,
$Q(x) = A^O(x)$.

In other words if there is an algorithm $A$ which uses oracle $O$ and solves problem $Q$.

If our reduction algorithm $A$ is polynomial-time we call it a polynomial-time Turing reduction or simply a Cook reduction and write $Q\leq^\mathsf{P}_T O$.

However we may want to put some restrictions on the way that the reduction algorithm interacts with its oracle. There are several restrictions that are studied but the most useful restriction is what is called many-one reductions (sometime also referred to as mapping reductions).

The idea here is that on a given input $x$, we perform some polynomial-time computation and generate $y$ that is an instance of the problem the oracle solves, then we ask the oracle and return the answer it gives us. We are allowed to ask a single question from the oracle and oracles answers is what will be returned.

More formally,

We say that problem $Q$ is many-one reducible to problem $O$ and write $Q \leq_m O$ iff
there is an algorithm $A$ such that for all inputs $x$,
$Q(x) = O(A(x))$.

When the reduction algorithm is polynomial-time we call it polynomial-time many-one reduction or simple Karp reduction and denote it by $Q \leq_m^\mathsf{P} O$.

The main reason for the interested in this particular non-interactive reduction is that it preserves $\mathsf{NP}$ problems: if a have a polynomial-time many-one reduction from a problem $A$ to an $\mathsf{NP}$ problem $B$, then $A$ is also in $\mathsf{NP}$.

The simple notion of reduction is one of the most fundamental notions in complexity theory along with $\mathsf{P}$ and $\mathsf{NP}$ and $\mathsf{NP}$-complete (which we will discuss below).

---

$\mathsf{NP}$-completeness: Universal $\mathsf{NP}$ Problems

OK, so far we have discussed the class of efficiently solvable problems ($\mathsf{P}$) and the class of problems efficiently verifiable problems ($\mathsf{NP}$). As we discussed above, both of these are upper-bounds. Let's focus our attention for now on problems inside $\mathsf{NP}$ as amazingly many natural problems turn out to be inside $\mathsf{NP}$.

Now sometimes we want to say that a problem is difficult to solve. But as we mentioned above we can't use lower-bounds for this purpose: theoretically they are exactly what we would like to prove, however in practice we haven't been very successful to prove lower-bounds and in general they are hard to prove as we mentioned above. Is there still a way to say that a problem is difficult to solve?

Here comes the notion of $\mathsf{NP}$-completeness. But before defining them let's have another look at reductions.

We can think of lower-bounds as absolute difficulty of problems. Then we can think of reductions as relative difficulty of problems. We can take a reductions from $A$ to $B$ as saying $A$ is easier than $B$. This is implicit in the $\leq$ notion we used for reductions. Formally, reductions give partial orders on problems.

If we can efficiently reduce a problem $A$ to another problem $B$ then $A$ should not be more difficult than $B$ to solve. The intuition is as follows:

Let $M^B$ be an efficient reduction from $A$ to $B$, i.e. $M$ is an efficient algorithm that uses $B$ and solves $A$. Let $N$ be an efficient algorithm that solves $B$. We can combine the efficient reduction $M^B$ and the efficient algorithm $N$ to obtain $M^N$ which is an efficient algorithm that solves $A$.

This is because we can use an efficient subroutine in an efficient algorithm (where each subroutine call costs one unit of time) and the result is an efficient algorithm. This is a very nice closure property of polynomial-time algorithms and $\mathsf{P}$, it doesn't hold for many other complexity classes.

Now that we have a relative way of comparing difficulty of problems we can ask which problems are most difficult among problems in $\mathsf{NP}$? We call such problems $\mathsf{NP}$-complete.

$\mathsf{NP}$-complete problems are the most difficult $\mathsf{NP}$ problems,
if we can solve an $\mathsf{NP}$-complete problem efficiently, we can solve all $\mathsf{NP}$ problems efficiently.

More formally, we say a decision problem $A$ is $\mathsf{NP}$-complete iff

$A$ is in $\mathsf{NP}$, and
for all $\mathsf{NP}$ problems $B$, $B$ is polynomial-time many-one reducible to $A$ ($B\leq_m^\mathsf{P} A$).

Another way to think about $\mathsf{NP}$-complete problems is to think about them as as the complexity version of universal Turing machines. An $\mathsf{NP}$-complete problem is universal among $\mathsf{NP}$ problems in a similar sense: you can use them to solve any $\mathsf{NP}$ problem.

This is one of the reasons that good SAT-solvers are important, particularly in the industry. SAT is $\mathsf{NP}$-complete (more on this below), so we can focus on designing very good algorithms (as much as we can) to solve SAT and then to solve any other problem in $\mathsf{NP}$, we can convert the problem instance to a SAT instance and then use an industrial quality highly optimized SAT-solver.

If a problem satisfies the second universality condition in the definition of $\mathsf{NP}$-completeness but is not known to be in $\mathsf{NP}$ or even when it is not in $\mathsf{NP}$ we call the problem $\mathsf{NP}$-hard. $\mathsf{NP}$-hardness is a way of saying that a problem is difficult (as long as there is some difficult problem in $\mathsf{NP}$). But I personally prefer to think about it as universality, so probably $\mathsf{NP}$-universal could have been a more correct name (as we don't know at the moment if they are really hard or it is just because we haven't been able to find a polynomial-time algorithm for them). The name also confuses people to incorrectly think of $\mathsf{NP}$-hard problems as problems which are absolutely hard to solve, we don't know that, we only know that they are as difficult as any $\mathsf{NP}$ problem to solve. Thought experts think it is unlikely it is still possible that all $\mathsf{NP}$ problems are easy and efficiently solvable. In other words, being as difficult as any other $\mathsf{NP}$ problem doesn't mean really difficult. That is only true if there is an $\mathsf{NP}$ problem which is absolutely hard.

Now the question are:

• Are there any $\mathsf{NP}$-complete problems?

• Do we know any of them?

I gave away the answer when we discussed SAT-solvers. The surprising thing is that many natural $\mathsf{NP}$ problems turn out to be $\mathsf{NP}$-complete (more on this below).

Before moving to examples, note that we can give similar definitions for other class of problems and define classes like $\mathsf{ExpTime}$-complete.

---

To be written...

$\mathsf{NP}$-complete Problems: There are Universal $\mathsf{NP}$ Problems in $\mathsf{NP}$

What does $\mathsf{NP}$-completeness mean for practice?

$\mathsf{P}$ vs. $\mathsf{NP}$

What's Next? Where To Go From Here?

Answer 2

More than useful mentioned answers, I recommend you highly to watch "Beyond Computation: The P vs NP Problem" by Michael Sipser. I think this video should be archived as one of the leading teaching video in computer science.!

Enjoy!

Answer 3

Simplest of them is P, problems solvable in polynomial time belongs here.

Then comes NP. Problems solvable in polynomial time on a non-deterministic Turing machine belongs here.

The hardness and completeness has to with reductions. A problem A is hard for a class C if every problem in C reduces to A. If problem A is hard for NP, or NP-hard, if every problem in NP reduces to A.

Finally, a problem is complete for a class C if it is in C and hard for C. In your case, problem A is complete for NP, or NP-complete, if every problem in NP reduces to A, and A is in NP.

To add to explanation of NP, a problem is in NP if and only if a solution can be verified in (deterministic) polynomial time. Consider any NP-complete problem you know, SAT, CLIQUE, SUBSET SUM, VERTEX COVER, etc. If you "get the solution", you can verify its correctness in polynomial time. They are, resp., truth assignments for variables, complete subgraph, subset of numbers and set of vertices that dominates all edges.