# 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

Last update: November 23, 2020