NP Definitions

Summary

We can define complexity classes and group problems into these groups based on how difficult they are to solve.

Contents

• Definitions
• Complexity Classes
• Examples
  • Satisfiability
  • k-colorings Problem
  • MST
  • Knapsack
    • Knapsack Search
• Reductions

Definitions

Intractable
Unlikely to be solved in time polynomial to its input size

Complexity Classes

NP
Class of all `search` problems. Could be class of all decision problems too, but not for this course. Non-deterministic polynomial time

Search Problem
A problem where we can efficiently verify solutions.

P
Class of search problems that are solvable in polynomial time. Polynomial time

$$P \subset NP$$

Search Problem (formal)
Form: Given instance I - find a solution S for I if one exists - output NO if I has no solutions Requirement: if given an instance I and solution S, then we can verify that S is a solution to I in polynomial (in |I|) time.

NP-Complete
Class of the hardest problems in NP but not in P.

Examples

Satisfiability

Input:

• Boolean formula f in CNF with n variables and m clauses

Output:

• Satisfying assignment, if one exists

k-colorings Problem

Input:

• Undirected graph G=(V,E) and integer k > 0

Output:

• Assign each vertex a color in ${ 1, \ldots, k }$ so that adjacent vertices get different colors and NO if no such coloring exists

Checking: Given G and a coloring, in O(m) time we can check that $\forall (v,w) \in E, \text{color}(v) \neq \text{color}(w)$

MST

Input:

• G=(V,E) with positive edge lengths

Output:

• Tree T with minimum weight

Checking: Given G and T, we can run BFS/DFS to check if T is a tree. Then we can run Kruskal’s or Prim’s to find an MST T’ and verify that w(T) = w(T’)

Knapsack

Input:

• n objects with integer weights and integer values
• Capacity B

Output:

• Subset S of objects with total weight at most B and maximum total value

Knapsack is not known to be in NP because we can’t check a given value against an optimal value like we did for an MST. We’d have to compare it against all possible values (O(nB), not polynomial time. We’d need O(n * logB))

Knapsack Search

A variant of knapsack that is known to be in NP

Input:

• n objects with integer weights and integer values
• Capacity B
• Goal g

Output:

• Subset S of objects with total weight at most B and value of at least g

Reductions

Given problems A and B (i.e. A=Colorings, B=SAT), $A \rightarrow B$ means reducing A to B.

Reduction
If we can solve problem B in polynomial time, then we can use that algorithm to solve A in polynomial time