Complexity classes

Nondeterministic Polynomial time (NP)

In this class we use the search problem definition.

Search problems

Note here we have.

Statement

There is an open problem.

P equals NP or P not equals NP

Satisfiability

SAT problem

The Satisfiability problem is in NP

k-colourings problem

Statement

The k-colourings problem is in NP

MST

MST

Minimum Spanning Tree problem is in NP

This proof was relatively easy as MST is a polynomial time problem. This is shown by what is above and Kruskal’s algorithm.

Knapsack problem

Statement

Whilst the Knapsack problem is of the correct form to be a search problem we can’t currently check if a solution is correct in polynomial time. Therefore the Knapsack problem isn’t known to be in NP.

Similarly we say that the Knapsack problem isn’t known to be in polynomial time either.

We say it isn’t known to be as there might be a super clever algorithm that happens to solve the Knapsack problem in polynomial time.

However, there is a variant of the problem that is in NP.

Statement

Here instead of having to check if a solution is maximal we can instead just check if it has enough value.

Knapsack-search is NP

Polynomial time and Nondeterministic Polynomial time

Note that NP isn’t Not Polynomial time. In fact we have the following result.

Polynomial time is a subset of NP-complete

The question is, are there problems that are in NP but are not in P?

NP-complete

If P not equal to NP then we would have a problem in NP that didn’t lie in P. Therefore the green region above would be non-empty.

Therefore lets look at the hardest problems in NP.

NP-hard

We define a many-one reduction as bellow.

Many-one reduction

However, we want to look at the hardest problems in NP.

NP-Complete

A classic NP-Complete problem is the SAT problem.

Reductions functionally

To show a many-one reduction from $A$ to $B$ you need to construct $f$ a way to transform an instance of problem $A$ into some input to the problem $B$. This needs to be done in polynomial time. Then the solution from solving $f(I)$ in problem $B$ should relate back to the solution of problem $A$. Either you should construct $h$ a way to transform the solution from problem $B$ into a solution to problem $A$ or forward on the fact that no solution can exist.

Therefore to show $A$ reduces to $B$ we need:

• Define $f$: Show how an instance of problem $A$ can be converted into an instance of problem $B$ in polynomial time.
• Define $h$: Show how a solution to the problem $B$ can be converted into a solution to problem $A$ in polynomial time.
• Proof: Show that a solution for $B$ exists if and only if a solution to $A$ exists.

Showing NP-Complete

To show a problem $A$ is NP-Complete need to show

• $A$ is in NP, and
• $A$ is NP-hard.

Generically showing $A$ is NP-hard, is ironically quite hard. However we get around this by having some NP-complete problems already, such as the SAT problem. Then to show $A$ is NP-hard we just need to show another NP-Complete problem reduces to it. So functionally we show:

• $A$ is NP, and
• there is some NP-complete problem $B$ that reduces to $A$.

Practice problems

From Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.