To properly classify problems we will sometimes need to define models of computation that do not exist in nature. Such is the case with nondeterminism, the topic of this lesson.
A nondeterministic Turing machine can make guesses and then verify whether that guess is correct. Let us consider the map coloring problem. Suppose you are presented with a map of a fictitious world and you want to give each country a color so no two bordering countries have the same color. How many colors do you need?
The famous Four Color Theorem states that four colors always suffice. Can one do it in three?
Let L be the set of maps that are 3-colorable. A nondeterministic Turing machine can "guess" the coloring and then verify quickly for every bordering pair of countries that they have different colors.
We let NP be the class of problems that use nondeterministic polynomial time. We can give an equivalent definition of NP using quantifiers: L is in NP if there is a polynomial p and a deterministic Turing machine M such that for all x, x is in L if and only if there is a w, |w| ≤ p(|x|) and M(x,w) accepts in time at most p(|x|).
The string w is called a witness. In the case of map coloring, w is the coloring of the countries.
Can we solve map coloring in deterministic polynomial-time? Is every NP problem computable in deterministic polynomial-time? Therein lies the most important question of all, which we will discuss in the next lesson.
The definition of NP misses an important piece. M must reject any x that is not in the language for all w.
ReplyDeleteIt doesn't matter--you can just add a clock and halt M(x,w) after p(|x|) steps and reject.
DeleteOK. I missed the “and only if”. Would the following be equivalent?
ReplyDeleteL is in NP if there is a polynomial p and a deterministic Turing machine M such that for all x in L, there is a w, |w| ≤ p(|x|) and M(x,w) accepts in time at most p(|x|), and for all x not in L, for all w, M(x,w) rejects.
Yes, that definition works.
Delete