# P vs. NP vs. NP-complete vs. NP-hard

##### November 25, 2018

`computer`

`science`

These definitions all refer to *how long it takes* for a program to run.

## P

- Polynomial
- efficiently solvable,
- Problems that can be solved in polynomial time,
- polynomial time: time taken is of the form O(n^c)

- Decision problems that can be solved efficiently.
- Efficient algorithms:
- are algorithms that use at most polynomial amount of computer resources,
- are algorithms that have polynomial worst-case running time.

- Formally, a decision problem Q is in P if:
- there is an efficient algorithm A for all inputs x:
- if Q(x) = YES then A(x) = YES,
- if Q(x) = NO then A(x) = NO,

- there is an efficient algorithm A for all inputs x:

## NP

- Non-deterministic polynomial,
- efficiently verifiable,
- Problems with efficient algorithms for verifying proofs/certificates/witnesses(sometime people use certificate or witness in place of proof),
- A program that solves a problem in non-deterministic polynomial(NP) time,
- not in polynomial time on a regular computer(deterministic Turing machine)
- BUT on polynomial time on a non-deterministic Turing machine
- a non-deterministic Turing machine can do everything a regular computer does and more

- Problems that cannot be solved, but verified in polynomial time,
- Class of problems which have efficient verifiers,
- Formally, a decision problem Q is in NP if:
- there is an efficient algorithm V called verifier for all inputs x:
- if Q(x) = YES then there is a proof y such that V(x, y) = YES,
- if Q(x) = NO then for all proofs y such that V(x, y) = NO,

- there is an efficient algorithm V called verifier for all inputs x:
- A decision problem is in NP if we can give an efficient verifier which is sound and complete:
**sound verifier:**a verifier which does not accept any proof when the answer is NO,**complete verifier:**a verifier which accepts at least one proof when the answer is YES.

**REMARK:**If any particular problem is said to be in NP and nothing else is said about it, then the fastest algorithm to solve this problem takes exponential time.**But**, it does**not**mean that there are better algorithms; it’s just that we do not know of that.**REMARK:**Stating that a problem is in NP space, does not mean that it’s hard to solve; it just means that it’s easy to verify, it’s an upper-bound on the difficulty of solving the problem.- REMARK: Many NP problems are easy to solve since 𝖯⊆𝖭𝖯.
- If a reduction algorithm A works in polynomial time, then it’s called
`polynomial time black box reduction`

or`Cook Reduction`

## NP-hard

- A problem X is NP-hard, if there’s an NP-complete problem Y such that Y can be reduced to X in polynomial time,
- A problem is NP-hard if it’s at least as hard as the hardest problem in NP-complete.
- If a problem satisfies the second condition of NP-completeness(the universal conditionality), then it’s NP-hard
- A way of saying that a problem is difficult
- NP-hardness = universality
- Therefore the name NP-universal would be a better name than NP-hard since it’s just that we don’t know if they’re easily solvable.

## NP-complete

- A problem that is both NP-hard and NP.
- The most difficult problems in NP to solve
- If we can solve an NP-complete problem efficiently, we can solve all NP problems efficiently.
- Many natural NP problems turns out to be NP-complete
- natural problem: a problem which people really care about solving but not an artificial one just to prove a point

## Overall Picture

Here is a nice picture to see a comparison of everything talked here.