Complexity Theory

Complexity Classes

Definition

Def Complexity Classes

• 
  They follows that

Alternative definition for : a problem is in if we have a polynomial time verification algorithm with polynomial size certificates/proofs.

Proposition

Prop

• and .
• and .
• and .
• and .

Theorem

Thrm Savitch’s Theorem
and .

Reductions

Definition

Def Polytime-Computable
is a polytime-computable function if some polynomial time Turing Machine exists that halts with just on its tape, when started on any input .

Definition

Def Polynomial Time Mapping-Reducible
is polynomial time mapping-reducible to , written , if a polytime-computable function exists. We also say it is a reduction from to .

Definition

Def Reduction
A reduction is a polytime-computable map where and such that
e.g. Reduction from ODD to EVEN: , so is odd iff is even.

Completeness & Hardness

Definition

Def
The definition of set is

Definition

Def
A language is said to be -complete if and . And is the set of such languages.

Proposition

Prop -complete problems are the hardest ones in .

Theorem

If and , then .

Corollary

If and for some , then .

Comment

List of known -complete problems:

• SAT (first problem proved ) and 3-SAT
• Graph-Colorability and 3-Graph-Colorability
• Independent Set and Vertex Cover
• Hamiltonian path
• Traveling Salesman Salesman Problem