# NP-Completeness

## Overview

• NP = non-deterministic polynomial
• Decision problems
• NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs
• More precisely, efficiently means by deterministic computations that can be performed in polynomial time

## Classes

### NP-Complete

• Decision problem which is NP and NP-hard
• A given solution to an NP-complete problem can be verified in polynomial time, there is no known efficient (i.e. polynomial time) method for finding a solution in the first place!
• Therefore NP-complete problems are most of the time addressed by heuristic methods and approximation algorithms.

### NP-Hard (non-deterministic polynomial acceptable problems)

Oooh, so NP-hard says that if we solve this problem, any NP problem can be solved in polynomial time, using this solution as a subroutine!

Assuming a solution for the NP-hard problem `H` takes 1 unit time, we can use the `H` 's solution to solve any NP problem `L` in polynomial time.

• "At least as hard as the hardest problems in NP"
• A problem `H` is NP-hard when every problem `L` in NP can be reduced in polynomial time to `H`

## Definitions

deterministic turing machine (DTM)
set of rules prescribes at most one action to be performed for any given situation. TL;DR: can only choose from one actions given the current state.
non-deterministic turing machine (NTM)
may have a set of rules that prescribes more than one action for any given situation. TL;DR: can potentially choose from multiple actions given the current state.