> For the complete documentation index, see [llms.txt](https://wiki.hanzheteng.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wiki.hanzheteng.com/algorithm/cs/complexity-classes-p-np.md).

# Complexity Classes (P, NP)

<figure><img src="/files/QGWJXY4BLuCg3AgVutme" alt="" width="563"><figcaption></figcaption></figure>

```
____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V
```

Notes on `Yes` or `No` entries:

* \* An NP problem that is also P is solvable in P time.
* \*\* An NP-Hard problem that is also NP-Complete is verifiable in P time.
* \*\*\* NP-Complete problems (all of which form a subset of NP-hard) might be. The rest of NP hard is not.

### Complexity Classes for Decision Problems

* Decision problem: A problem with a yes or no answer.
  * Note that the following definitions and discussions are centered about the decision problem (or if a solution is verifiable), and do not mention if you can find the solution (or if the problem is solvable).
* P is a complexity class that represents the set of all decision problems that can be solved in polynomial time.
  * That is, given an instance of the problem, the answer yes or no can be decided in polynomial time.
* NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time.
  * This means that if someone gives us an instance of the problem and a certificate (sometimes called a witness) to the answer being yes, we can check that it is correct in polynomial time.
  * Note that NP is for Nondeterministic Polynomial time; not non-polynomial time.
* NP-Complete: NP-Complete is a complexity class which represents the set of all problems `X` in NP for which it is possible to reduce any other NP problem `Y` to `X` in polynomial time.
  * Intuitively this means that we can solve `Y` quickly if we know how to solve `X` quickly.&#x20;
  * Precisely, `Y` is reducible to `X`, if there is a polynomial time algorithm `f` to transform instances `y` of `Y` to instances `x = f(y)` of `X` in polynomial time, with the property that the answer to `y` is yes, if and only if the answer to `f(y)` is yes.
* NP-Hard: Intuitively, these are the problems that are at least as hard as the NP-complete problems.
  * Note that NP-hard problems do not have to be in NP, and they do not have to be decision problems.
  * The precise definition here is that a problem X is NP-hard, if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time.

References: <https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard>