Tags: Computer Science, Incomplete, Notes

Computational complexity

P: problems solvable in polynomial time
EXP: problems solvable in exponential time
R (Recursive) : problems solvable in finite time

P ⊆ EXP ⊆ R

NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE

Most problems are unsolvable

Examples

Negative weight cycle detection (P)
Chessboard (EXP)
Tetris (EXP, we think it’s not in P but not sure)
Alting problem (not in R, unsolvable, no algorithm)

Most decision problems are uncomputable (not in R)

program: can be encoded in a binary string -> can be represented

by a number (integer N).

decision problem: can be represented as a function that map
input to T or F.

function:input -> {yes, no}

input is a binary string

f(input) = result

Any real number between 0 and 1 can be represented as a series
of bits.

Decision problem are in R, programs are in N

Number of elements in R is greater than N

|R| > > |N|

Almost every problem is unsolvable by any program.

NP

P ⊆ NP ⊆ EXP ⊆ R

Solvable in polynomial time via a “lucky” algorithm.

Lucky algorithm: random but solve problem on the first guess =
Nondeterministic model

Nondeterministic model:

Theoretical model of computation.
Algo makes guesses -> yes, no.
guesses are guaranteed to lead to yes if possible.

NP: decisions problems with solutions that can be checked in
polynomial time.

when ever answer = yes, can prove it, and check that proof in
polynomial time

Tetris is in NP

Proof: sequence of moves to make

P != NP: you can’t engineer luck

Solving problems is harder than checking solutions

Harder to generate the proof of a theorem than to check a proof of
a theorem.

Claim

If P != NP then Tetris is in NP - P

Why: Tetris is NP-hard

NP-hard: as hard as every problem in NP.

Tetris is NP-complete
TSP is NP-complete (shortest path in 2D is polynomial, in 3D it is NP-complete.
Minesweeper, Sudoku, most puzzles

NP-complete (both in NP and NP-hard)

Chess is EXP-complete

EXP-hard: as hard as every problem in EXP…

Reduction (ex: Graph reduction)

Convert a problem into a known problem we know how to solve

A->B: convert problem A into problem B

Meaning “A->B”: B is at least as hard as A

unweighted shortest paths -> weighted shortest paths
min-product path -> shortest path
longest path -> shortest path
3-partition -> Tetris:
3-partition is at least as hard as Tetris

All NP-complete problems can be reduced to each others.

Computational Complexity