Computer Science 456/656
Automata and Formal Languages
P = NP? The most famous open question in all of computer
science. What does this mean? What does it mean in practical terms?
Language = Problem. A 0-1 problem is a problem where
the answer is always 0 or 1. A 0-1 problem P is considered to be a language
L by encoding each problem instance as a string, and then letting L be
the set of all encodings of such instances where the answer is 1.
Conversely, every language L is a 0-1 problem P. An instance of P
is a string over L's alphabet, and the answer is 1 if that string is in L,
0 if it is not.
Therefore, we can talk about languages and 0-1 problems interchangeably.
A function F(n) is said to be polynomial
if F(n) = O(nk) for some constant k.
A language L is said to be polynomial time
if there is some Turing machine T and some
polynomial function F(n) such that
-
L is accepted by T.
-
If w is a string of length n in L,
then T accepts w by a computation whose number of steps does not
exceed F(n).
The class of polynomial time languages is sometimes abbreviated
P-Time or just P.
A language L is said to be
non-deterministic polynomial time
if there is some non-deterministic Turing machine T and some
polynomial function F(n) such that
-
L is accepted by T.
-
If w is a string of length n in L,
then T accepts w by a computation whose number of steps does not
exceed F(n).
The class of non-deterministic
polynomial time languages is sometimes abbreviated
NP-Time or just NP.
Trivially, P is a subclass of NP. Is it true that every non-deterministic
polynomial time language is polynomial time? Most experts believe that
the answer is no, but no one has proved it.
Even though the P=NP question is open, there are languages which are known
to be as hard as an NP language can be. These are called
NP-complete languages. Here are the amazing properties
of such a language.
-
Every NP-complete language is in the class NP.
-
If any NP-complete language is in the class P, then P = NP.
So, to settle the most important open question in computer science, you
just have to find a polynomial time algorithm for
only one of the problems listed below, or prove that
there isn't one. How hard could that be?
-
The 0-1 traveling salesman problem.
-
The k-clique problem.
-
The 0-1 knapsack problem.
-
Boolean satisfiability.
-
Integer programming.
-
The 0-1 limited degree spanning tree problem.