Contents

Complexity Classes

Polynomial Time

Exponential Time

Nondeterministic Polynomial

Classes

P - Set of deterministic algorithms taking polynomial time NP - Non deterministic algorithms taking polynomial time

CNF - Satisfiability

Methods to show relation

Reduction

Take one problem’s and convert it to another’s formula Conversion should be done in polynomial time

NP Hard

If reduced by satisfiability

NP Complete

Existing ND algorithm