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

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.

-
It's a formal object with a formal definition. I have found most "simple" explanations to be lacking. If you have problems understanding the definitions, what are you doing in a class about complexity theory? (Serious question.) Just by the way, Wikipedia is not a very good reference for TCS. – Raphael Feb 6 at 22:34
Not all you know is true: NPC (NP complete) is a subset of NP, not the other way around. Completeness always includes being an element of the class the problem is complete for. Furthermore NP is not a subset of NP-hard, since not every problem in NP is hard. – frafl Feb 6 at 23:34
@frafl: "not every problem in NP is hard" -- which remains to be shown. – Raphael Feb 7 at 7:08
@Raphael: That actually depends on the type of reduction you use. I thought of polynomial time many one reductions, where $\emptyset \notin NPC$. – frafl Feb 7 at 10:01

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

## What's Next? Where To Go From Here?

-
In relation to your intro, readers might be interested in “NP-complete” optimization problems and Decision problems vs “real” problems that aren't yes-or-no. – Raphael Feb 7 at 7:10
@Kaveh That's an awesome post, thanks. I did do decidability before this section in the class, but I'm a bit behind in my understanding of proving undecidability. I don't know if this has anything to do with my lack of understanding with complexity though. – agent154 Feb 7 at 16:28
I have read many complexity books from intro level(including Sipser's) to more advanced. I have no problem with abstract math(e.g. I am able to read Lang's Algebra). This answer is the best to explain NP vs. P. I would suggest you to spend more time on polishing it and make it lecture notes. It can help a lot people. – scaaahu Feb 19 at 4:20
@scaaahu, thank you for the kind remark and also for the suggestions. I planning to complete and polish this soon. – Kaveh Feb 19 at 5:20
This answer should be made as a reference answer. All future basic P/NP type questions should be referred to this first. Very fluid description! – Paresh Feb 19 at 22:30

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!

-
 Agreed! Such an excellent introduction. – Marc Khoury Feb 6 at 21:58 Interestingly, my textbook is by him. It isn't a horrible book, but it leaves some to be desired. – agent154 Feb 7 at 3:44

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.

-
The crucial part is to explain reductions in a simple, but not misleading way. – frafl Feb 6 at 23:36