# NP-Completeness

## Table of Contents

## 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*

- More precisely,

## Classes

### NP

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