NP Completeness

Many problems seems impossible to solve efficiently. Here we only consider decision problems, that is, a problem with yes or no answers. It is also called Boolean satisfiability problem.

P problem: Problem that is polynomial-time solvable. O(n^k) worst case running time.
Class P: the set of all polynomial-time solvable problems.

NP: a problem is NP if 1. solution always have length polynomial in input size. 2. proposed solution can be verified in polynomial time. A traverlling sales man problem is NP. Notice that the NP is not non-P, it stands for non-deterministic poly-normal time, in short , NP is a problem that if we somehow guess an answer, the answer can be verified in polynomial time.

NP-Completeness Problem: Problem that is the hardest problem in NP and every problem in NP can be reduced from this problem. The travelling sales man problem for example, is one of them. Cook-Levin theorem: there exist a NP-complete problem. The problem that Cook-Levin theorem proofs is the 3SAT problem:

In computer science, Boolean, or propositional, satisfiability (often written SATISFIABILITY or abbreviated SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it establishes if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE. If no such assignments exist, the function expressed by the formula is identically FALSE for all possible variable assignments. In this latter case, it is called unsatisfiable, otherwise satisfiable. For example, the formula “a AND NOT b” is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, “a AND NOT a” is unsatisfiable.

This problem can be verified in polynomial time so it is NP. and all the problems in NP is easier than this problem. Easier means the problem can be reduced in polynomial time to another problem if A can be solved by calling solution for problem B polynomial time , we say that A can be reduced to B and A is easier than B. (A < B) Although it may take longer to solve A then B, A is still easier than B. we could solve it). NP-complete problem are those hardest problem in NP.

To prove a problem P to be NP-complete, you need to find another problem P' which is already known to be NP-complete. Then prove that P' can reduces to P (P' is easier than P). which proves that P is at least as hard as P so P is also NP-Complete.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s