> 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>


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://wiki.hanzheteng.com/algorithm/cs/complexity-classes-p-np.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.