Jimmy Kong
Math 97 – Senior Conference
Professor Thomas Hunter
March 21, 2001
INTRODUCTION
We have all encountered difficult problems before. Sometimes we feel that they are intuitively hard, that it is the very nature of the problem for it to possess a complex solution. Other times we have a sense that problems are not as hard as they appear. If one examines them well enough, perhaps they would discover a clever manipulation or application that leads to a simple a solution. The problem of P versus NP is essentially an in depth look at many hard problems and their relations to easier problems. Problems in P only require a polynomial number of steps to solve. Problems in NP are those that could be checked in a polynomial number of steps. Most theorists and mathematicians who have studied P and NP believe that there exist problems that could be checked in polynomial time (in NP), but requires beyond polynomial time to solve (not in P). There are plenty of NP problems that are not known to be solvable in polynomial time, but none of them have ever been proven to not be in P. Do all problems that can be checked in polynomial time actually have solutions that only take a polynomial amount of time? Does P equal NP? To this day this question remains unsolved, so there is no proof of this to present. We can however express the meaning of the question more clearly. To do so we shall describe the complexity classes P and NP along with the many ideas attached to the theory of computation.
HISTORY
OF COMPUTATION
In the 1930s before the existence of computers logicians and mathematician such as Alan Turing developed the classical theory of computation. They began with an interest in answering questions like “Given a mathematical proposition, is the statement true or false?” It was not clear when there was an answer and when there was not. This idea of computability led them formulate a more concrete system of describing problems. With that system they were able to translate many problems into a language that can be read and analyzed by a machine. The machine they used for this purpose was called the Turing machine. It could take an infinitely long string of input, had no bounds on its memory storage capacity, and could continue operating on forever. Now even though a Turing machine was entirely hypothetical, the studies into its design and processes lead to the development of computers.
TURING
MACHINES
The only machines we shall concern ourselves with would be Turing machines. They can perform any task any modern day computer can, although it may have to carry out several times more operations. A Turing machine is composed of three basic parts. The first is the finite state control center, which handles all the actions performed by the machine. One can simply imagine this to be a box. The second component is a strip of tape that is infinitely long in both directions. This tape is what stores the data. Extending from the box is a wire with head at the end called the read-write head. This device reads data from and writes data to the tape, taking its instructions from the finite state control. There are actually many variations of the Turing machine, but this is a rather simple one.
FORMULATION OF PROBLEMS
The first step in
analyzing problems is the formalization of its structures. A problem begins
with an instance, which contains the given information. Problems also have
solutions. An abstract problem is defined as an association on a set of
instances and a set of solutions. A decision problem is a problem in which
the solution set is the set {0,1}. These are also called Yes/No problems
because they can correspond to questions with yes or no answers.
A solution of 1 represents yes or true, while a 0 represents no
or false. All the problems we shall discuss will be decision problems.
Many of the problems we encounter in the real world are not explicitly decision
problems, but are optimization problems. In these problems there is a value
desired to be maximized or minimized. Optimization problems could be translated
into decision problems by simply introducing a bound into the instance.
Questions like “Does a path exist from point A to point B of length less than k?”
and “Can more than k queens be placed on an n´n
chess board in positions such that none can capture another?” are examples of
optimization problems transformed into decision problems.
LANGUAGES
Machines don’t operate at an abstract level. We want a method of wording our problems so that machines will be accept them. We begin by defining the language that the language accepted by a machine. A language begins with an alphabet. An alphabet is a set of symbols. We want to choose alphabets that are rings. Why? The fundamental operations of a machine are all arithmetic. Likewise the basic of operations of rings are all arithmetic. Rings have nice closure properties under these operations. We need our language to be closed, since we don’t want a machine to produce a result it does not understand. The alphabet we shall concern ourselves with is the set {0,1} since it is a simple and finite ring and because computers generally operate with binary strings. We will call the set of all binary strings {0,1}*. A language L is simply a set of the strings over an alphabet. In our case, any subset {0,1}* is a language. LÎ{0,1}*.
To translate abstract problems into machine language, they would have to be encoded. An encoding is defined as a mapping of set of abstract objects into set of binary strings. After encoding our problem becomes a concrete problem. A concrete problem is one in which the instance sets and solution sets are sets of binary strings. Here are two examples of encoding. The first maps base ten integers into their base two form. The second maps some of the basic colors of light into binary strings by the having the first bit represent the presence of red, the second blue, and the third green.
Example 1: {1, 2, 3, 4, 5, 6, … } à {1, 10, 11, 100, 101, 110, …}
Example 2: {red, blue, green, white, …} à {100, 010, 001, 111, …}
DECIDABILITY
If all the instances of a decision problem are translated as all the strings in a language L, then we can think of L as the language of that decision problem. Languages are essentially problems expressed in the machine code form. Algorithms are the systematic procedures running on machines that solve problems. They do so by performing operations on a string in the language of the problem to output an answer.
If it cannot be determined whether or not a problem can be solved by any algorithm we say the problem is undecidable. Undecidable problems are not necessarily complicated ones, but they run on indefinitely and perhaps never terminate. If our algorithm A is given an input string x and outputs a 1, “A(x)=1”, we say A accepts x. If given input string x, algorithm A outputs a 0, “A(x)=0”, we say A rejects x. The language accepted by an algorithm A is the set of all binary strings that A accepts. If the algorithm accepts all the strings in our language, “"xÎL, A(x)=1”, it is still not enough to claim the language is accepted. We need to the added condition that all strings not in the language are not accepted. “xÏL à A(x)¹1”
Definition:
L = {xÎ{0,1}*,
A(x)=1} L is the language accepted by A
An algorithm decides a language if the algorithm accepts or rejects all binary strings. Note that it is not enough that the algorithm decides just the strings in a specific language. It needs to decide all possible strings. This way if an algorithm decides a language one can be sure that any input is either accepted or rejected, even those that are not in our language. Thus an algorithm decides all languages or decides none. If it does not decide a language, we are unsure whether it terminates.
Definition:
"xÎ{0,1}*, A(x)=1 or A(x)=0 L is a language decided by A
COMPLEXITY
When studying problems we not only want to differentiate them by computability, but also by their complexity. Complexity classes are used to show a hierarchy of the complexities of problems. Since we know that decision problems all have the same solution set {0,1}, the only factor that makes one problem more complicated than another is its language. Thus the complexity of languages can be measured by the amount of basic computations the algorithms that run under them require.
The running time of an algorithm used to solve a problem, normally varies depending on the size of the input. In addition, because algorithms are systematic, a relatively simple expression can usually be found that shows how the input size effects the running time. Let n represent the size of the input. An algorithm that requires f(n) basic operations to compute a solution is said to have f(n) running time. The basic operations of a machine are never more complicated than simple arithmetic. Therefore actions such as incrementing a number are considered single basic operations, while actions such as multiplication count as compilations of multiple basic operations.
Running times are expressed using the asymptotic upper bound notation, also called the O-notation. When we say f(n) is order g(n), written f(n) = O(g(n)), we will take it to mean that the actual running time of f(n) is an expression that is bounded above by a constant times g(n) for all large n. That is, as n goes to infinity, f(n)<cg(n) where c is a positive constant.
Definition:
Let f(n)and g(n) be
positive increasing functions. f(n)
= O(g(n)) if
O(g(n)) = {f(n): $ constants c and n0 such that 0£f(n)£ g(n) for all n ³ n0}.
We say f(n) is order g(n).
Examples:
7n3 + n = O(n3) 25n + n99 = O(25n) 6n! = O(n!) 8n2 = O(n!)
In the examples above, the running times of 7n3 + n2 and 8n2 are both polynomial running times while the others are not. Note that even though 8n2 = O(n!), it also happens that 8n2 = O(n2) making it polynomial time. To define complexity formally, we will return to the context of decidability. An algorithm accepts a string in order g(n) time if the algorithm accepts the string and the number of operations it performed is order g(n).
Definition:
An algorithm A accepts a language L in polynomial time if
for every string xÎL, A accepts x in O(nk) time where k is a constant.
Definition:
An algorithm A decides a language L in polynomial time if
for all strings xÎ{0,1}*, x is accepted or rejected by A in O(nk) time.
COMPLEXITY
CLASS P
The complexity class P is the class of Polynomial Time languages. This set was previously referred to as the set of problems solvable in polynomial time. Now with the knowledge of decidability and complexity we define P formally.
Definition:
P = {L Í{0,1}*
: $
algorithm A that decides L in polynomial time.}
If possible, we always want to work with languages in P. We consider polynomial time algorithms tractable. Polynomials are closed under addition, multiplication and composition. Algorithms running in polynomial time on one machine run in polynomial time on all machine.
As defined P is the class of languages decided in polynomial time. This class also happens to be the same as the class of languages accepted in polynomial time. To prove this we will show that each class is a subset of the other.
THEOREM [CLR]
P = {L Í{0,1}* : $ algorithm A that accepts L in polynomial time.}
Proof:
Let S be set of all languages L accepted by an algorithm A in polynomial time.
First show P Í S. This is fairly trivial.
Look at A
which decides some language L. Given any string x in L, A
outputs either 0 or 1 after cnk steps or less. Let A¢ be the algorithm running alongside A that mimics A
except that A¢
outputs 1 whenever A outputs 0.
A¢(x) = 1 for all x in L, in at most cnk steps. Adding A¢ does not increase running time by more than poly factor. Thus L can be accepted in poly time.
Now show S Í P.
Look at A which accepts L.
Given any string x in L, A outputs 1 after cnk
operations or less. We need all to decide all x
Î{0,1}*, so we must
consider all strings that are rejected by A, as well as ones that may
not halt.
Let A¢ be an algorithm that mimics A in every way for time T£cnk, but after cnk operation A¢ outputs 0, rejecting x. A¢ = 0 or 1 for all xÎ{0,1}*, and performs no more that cnk operations.
Implementing A¢ does not increase the run time by more than poly factor.
Therefore L can be decided in poly time, and we have that P = S.
ÿ Q.E.D.
PROBLEMS IN P
An example of a problem in P is the Shortest Path Problem. It is a generally well-known problem in computer science. Simply stated the task is to find the shortest path between two vertices in a graph. As mentioned before, to convert it into a decision problem we introduce a value we want to minimize or maximize. Formally stated it asks, “Given set of vertices, set of weighted edges, two specific vertices a and b, and a positive integer k, does there exist a path from a to b with totally distance of at most k?”
It is not difficult to prove that the Shortest Path Problem is solvable in polynomial time. There exists an easy algorithm that can solve it in n2 operations or less. There are also other algorithms that are more efficient than that specific one in running time. Guassian Elimination is another example of a problem in P.
VERIFICATION
On the other side
of the mystery are the NP problems. To understand this class of problems we
will first describe how an algorithm verifies a language. Let x and y
both be strings in {0,1}*. We will allow our algorithm A to accept
two input arguments. When we write “A(x,y)=1”, it means
the algorithm which was given both x and y as inputs halts in an
accepting state. Likewise “A(x,y)=0” means the algorithm
rejected the strings.
Definition:
An algorithm A verifies the language L if
L = {xÎ{0,1}*: there exists yÎ{0,1}* such that A(x,y) = 1.}
The string y is called a guess. It is also sometimes referred to as a certificate or a witness. The string x is supposed to be our original problem instance while y can be thought of as a guess at the solution to the problem. In a sense the algorithm A, is no longer an algorithm that solves anything, but rather performs a check. The new instance for this problem is the concatenation of the strings, and the decision problem is asking whether or not y is a correct solution to a problem instance of x.
We don not just say A verifies a language if for all strings x in the language L we have A(x,y)=1, because we want the verification process to also have integrity. That is, if x is not in the language L, then we know A(x, y) does not produce a 1. If a string is not in our language, we do not want the algorithm to be fooled into verifying that it is.
Definition:
A verifies L in polynomial time if
L = {xÎ{0,1}*: there exists a guess y with |y| = O(|x|c) such that A(x,y)=1}
and A(x,y) runs in polynomial time.
For polynomial time verification, there is the added
condition that the length of our guess y must be not more than a
polynomial order larger than our original problem instance x, |y|
is order O(|x|c). This is there to prevent outrageous
guesses to be inputted, in which y could be the entire procedure to
solve the problem rather than just a check. If we allow for such a thing then
all problems that can be checked in a finite amount of time, even exponential
time and beyond, would be included.
COMPLEXITY CLASS NP
The languages in the class of Nondeterministic Polynomial Time problems, or NP problems have two basic properties. The first is that any guess to the problem solution can be checked to be valid in polynomial time. The second property is that this certification process has integrity. Both of these properties are covered in our definitions of verification.
Definition:
NP = {L Í{0,1}* : $ algorithm A that verifies L in polynomial time.}
It is clear that any language L accepted in polynomial time is in NP, since verifying an answer does not take you longer than solving the problem. So P Í NP is trivial. If just a single language L in NP can be found such that L is proven not to be in P then you have proven P¹NP. No one has succeeded in this yet, however there exist many examples of NP problems that are not known to be in P. Some of these are listed here.
Given an integer c, find two integers that are non-trivial factors of it.
Knapsack Problem
This is also known as the Subset Summing Problem.
Given an integer c
and set of integers {x1, x2,… xn}
is there a subset S such that the sum of elements in S equals c?
Hamiltonian Cycle Problem
Given a set of vertices and a set of edges does a tour exist? A tour, also known as a Hamiltonian cycle, is a cycle in a graph where every vertex in the graph is visited exactly once along the cycle.
Traveling Salesman Problem
This is it stated as a decision problem.
Given a set of vertices, a set of weighted edges, and a positive integer k, does there exist a tour (Hamiltonian cycle) with total distance of at most k?
REDUCIBILITY
An additional method of sorting the complexity of problems we would want to use is the reducibility of specialized problems into broader ones. We can think of a problem Q as being reducible to another problem Q¢ if it can be easily reworded as instance of Q¢. Then if we solve Q¢, we solve Q.
Example: Problem Q: Given x, y, and z. Is x2 + y2 = z2?
Problem Q¢: Given w, x, y, and z. Is x2 + y2 = w2 + z2?
In our example, Q is easily rephrased as a special case of Q¢ when w=0. From this it is apparent that Q is essentially no harder to solve than Q¢. The definition of reducibility, is included in the following definition of reducibility in polynomial time.
Definition:
L1 is reducible to L2 in polynomial time, written L1 £P L2, if
$ a function f:{0,1}* à {0,1}* such that
"xÎ{0,1}*, xÎL1 if and only if f(x)Î L2, where f is computed by an algorithm F running in polynomial time.
In the definition above f is called the reduction function. The algorithm F is called the reduction algorithm. One set of problems called NP-Hard problems consists of problems where all NP problems are reducible to them. In fact all languages in NP are reducible to each single language the set of NP-Hard languages. NP problems are no harder than NP-Hard problems. Despite the name given to them, NP-Hard problems are not defined as a subclass of NP problems.
Definition:
A language L is NP-Hard if L¢ £P L for every L¢ÎNP.
NP-COMPLETE PROBLEMS
Problems that have NP-Completeness are the ones that are NP-Hard problems that can be verified in polynomial time. NP-Complete problems could be the thought of the hardest problems in NP. These problems have been studied closely as they are a possible link that ties the P and NP complexity classes.
Definition:
A language L is NP-Complete if LÎ NP and L is NP-Hard.
The Circuit Satisfiability Problem commonly called SAT is an NP-Complete problem that can be used as a basis for a lot of NP-Completeness proofs. Many NP-Complete problems can be shown to be reducible to the SAT directly or to a problem that was reducible to SAT. In the Circuit Satisfiability problem, we are presented with a particular circuit board setup, full of various logical gates such as AND, OR, and NOT. The input is in {0,1}* and the output is either 0 or 1. If we desired a specific output of a 0 or a 1, there is no easy way known to figure out what input set will produce it. Indeed it is possible that a given output is always or never the case. Checking to see whether any given input set gives us the desired output however can be done in a constant number of operations, equal to the number of gates. Thus we see easily that SAT is in NP.
Proposition: (as stated by Stephen Cook)
a. If L1 £P L2 and L2 Î P, then L1 Î P
b. If L1 £P L2 where L1 is NP-Complete and L2 Î NP, then L2 is NP-Complete
c. If L is NP-complete and L Î P, then P = NP
By applying statement (b) of the proposition, NP-Completeness can be proven by showing that the problem is in NP and then proving that it can be reduced to a known NP-Complete problem. The Knapsack Problem, Hamiltonian Cycle Problem (HP) and Traveling Salesman Problem (TSP) can all be proven this way. The chain of reducibility relations goes the following way: CIRCUIT-SAT £P HP £P TSP.
What is notable
about proposition (c) is that it suggests method of the possibly solving the P
versus NP puzzle. If we come up with any algorithm that solves an NP-Complete
problem in polynomial time, then we have proven P = NP. Yet no one has come up
with such a proof.
CONCLUSION
Most mathematicians, logicians, and theorists today believe that P ¹ NP. In fact many people in the world are gambling on this hunch. The cryptography systems used in the security of corporate firms and in the encryption of transactions over the Internet, would no longer be practical if they were solvable in polynomial time. On the other hand there are some benefits we receive if it does turn out that P = NP. Algorithms we use to solve hard problems such as the Traveling Salesman could be improved to run in polynomial time.
The study of the complexity classes and other areas of the theory of computation have allowed for many valuable discoveries. Sometimes these findings marvel us such as the revelation of NP-Complete problems. The simple notion that all problems verifiable in polynomial time are reducible to NP-Complete problems, including themselves, offers a feeling of wonder about the universe. In a sense they are all simply manifestations one single problem. Whether or not the grand mystery of the complexity classes P and NP will ever be solved, the discoveries that have arisen and the ones yet to be found in the exploration of computation theory will continue to be significant contributions to both computer science and mathematics.
1) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, McGraw-Hill Book Company, New York, 1997
2) Stephen Cook, The P versus NP Problem, University of Toronto, Preprint
3) Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale, Complexity and Real Computation, Springer-Verlag New York, Inc., 1998
Who Wants to be a Math Millionaire?: P vs. NP
Miller Maley, IDA Center for Communications Research
BiCollege Math Colloquium Talk,
Haverford College, Oct 30, 2000
http://www.claymath.org/prize_problems/index.htm
http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Turing.html