Comment on page

# Complexity Classes (P, NP)

____________________________________________________________

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

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

Last modified 6mo ago