# Complexity

## Overview

- Complexity classes are a way of categorizing problems by difficulty
- There are two kind of problems:
*search*and*verification*problems

### Example: Sorting

**Search version:**input a list of numbers X and output same list in sorted order (call it Y)**Verification version:**input a list of numbers X and another list Y, and output "YES" if Y is sorted version of X, "NO" otherwise

## Classes

### P

- Problems are in this class, if there exists a PTIME (polynomial-time, runs in \(O(f(n))\), where \(f\) is polynomial) algorithm that
*solves*the problem

### NP

- Problems are in this class, if there exists a PTIME algorithm, that
*verifies*the problem, but are not necessarily solveable in PTIME

**Reducibility:** Given an instance of a hard problem, we can construct an instance of another problem, whose solution will also solve the first problem

#### NP-complete

- If two problems in NP can be reduced to each other, are in this class
- A solution for
*any*of these would give us a solution to*all*of these problems

#### NP-hard

- These problems are
*at least*as hard as the*hardest*problem in NP-complete

### P vs. NP

**Is P=NP?**

**Yes**: \(P = NP\) means that for every problem that has an efficiently verifiable solution, we can find that solution efficiently as well**No**: \(P \neq NP\) means that it is*impossible*to find a general algorithm that will correctly and accurately solve an NP-complete problem all the time

## References

- Beyond Computation: The P vs NP Problem (video)
- The GĂ¶del Phenomena in Mathematics: A Modern View
- What are P, NP, NP-complete and NP-hard? (Quora)

Last update: November 23, 2020