(Sept 17, 2013)
Our little plan is to write a series of posts discussing a sequence of optimization problems. Before we dive into them, it is cool to learn a rigorous treatment of standard complexity notions P, NP, NP-hard and so forth. This is how this article arises.
The materials below come from the book GLS.
There are two types of problems that we are concerned. The first one is optimization problems, for example, linear programming (LP) problem, which is to compute . In this case the inputs (or instances) are two vectors and a matrix , while the output (or solution) is a vector (the minimizer). The second type is called decision problems which the output of the problem must be either “Yes” or “No”. For example, given a graph , does there exist a Hamiltonian cycle? This is a decision problem.
Decision problems and optimization problems are closely related, as we will see later.
We need an encoding scheme, which can convert every instance or solution into finite 0-1 string. Here the encoding scheme of our interest is binary representation. Let be the set of all finite 0-1 strings. For every , we let be its length.
First we define the meaning of a problem. Like the examples above, the key ingredients of a problem should be inputs (usually called ) and outputs (usually called ).
Definition 1. A problem is a subset of such that for any there exists such that .
Notice that “No solution” is also a solution to a problem.
The next step is to give a definition to “algorithm” which can solve a problem. We shall interchange the words “algorithm” and “Turing machine” (or simply machine). We are going to define a -tape Turing machine. A tape is an infinite 0-1-blank string. A -tape machine has tapes, and heads of which each one starts at the first cell of each tape, reads, writes or erases the entry, can move to the left or right, or can stay. Also a machine includes a central unit of states, especially a beginning state and an end state . The machine starts at state and works until state . Before we state the definition let us see an example of how a machine works.
Example 1. Here is a Turing machine which solves the problem of adding a binary number by 1. The states and actions are:
B: Search to the right for a blank. After reaching a blank, move the head to the left. Go to state C.
C: When reaching 0 replace it by 1 and then go to E. When reaching 1 replace it by 0 and stay at C. When reaching “blank” replace it by 1 and go to E. Move the head to the left no matter in which situation.
Suppose we want to compute 101+1. So the input is 101. At the state B the head points to leftmost 1. Now search to the right until the blank next to rightmost 1. Then move the head to the left and change the state to C. Now replace rightmost 1 by 0 and the middle zero by 1. Then go to state E and stop. The result will be 110 (which is expected).
(Sept 21, 2013)
Definition 2. Denote by the space of infinite 0-1-blank strings. A Turing machine is a 6-tuple ( is the upper case of ) such that:
is a finite set of states
specifies the change of states.
specifies the change of the letters in each tape.
specifies the movement of heads.
Definition 3. We say solves the problem if for any input , we set , to the -tapes of at the beginning state . Then, after a finite number of moves on read-write heads, it stops at state while is such that .
The next thing is to define a “polynomial time algorithm”. Given a problem and suppose solves . For any input , we define as the number of steps in which reaches state from state . The running time function for solving is a function () given by:
Since there are only finitely many 0-1 strings of length not exceeding , the maximum in above definition makes sense.
Definition 4. We say is a polynomial time algorithm solving if there is polynomial for which for all .
(Oct 9, 2013)
Now we restrict our discussion to decision problems, that are “Yes” or “No” problems. The classes P, NP etc. are defined in terms of decision problems.
Definition 5. A decision problem (DP) is a problem such that: For any , exactly or . Also, if , then or .
As we may know, NP problems are those decision problems such that if we guess the answer to the problem is “Yes”, then there is a polynomial length verification of this “Yes”. To be precise,
The polynomial in the above definition is to make sure the checking input cannot have too long length. In detail, it has to be controlled by that of .
By setting , one sees that . One of the Millennium Prize Problems asks if . Simply put, is there a decision problem in NP which is also in P? This is still unknown.
(Nov 9, 2013)
Intuitively, NP-complete problems are the hard decision problems, in terms of: all NP problems can be transformed to them in polynomial time.
Definition 6. Given two DPs and . A polynomial transformation from to is an algorithm such that given an instance of , produces an instance of in polynomial time such that
if and only if .
Definition 7. A DP is said to be NP-complete if any problem can be polynomial transformed to .
Therefore if an NP-complete problem is in P, then we have P = NP. Since people don’t believe P = NP, we have nothing more to do on a DP after realizing it as NP-complete.
Example 2 (Linear Programming). We can associate a decision problem naturally to a given optimization problem as follows: Given , is there some such that ? Indeed these two problems are equivalent: once we can solve the decision problem, we can use binary search algorithm to solve the optimization problem. Clearly the decision problem of LP is in NP. In 1979 Khachiyan discovered Ellipsoid Method which explains that LP is actually in P. Before 1979, Simplex Method was discovered by George Dantzig for solving LP. Simplex Method cannot be used to show LP is in P because one can construct some artificial example that cannot be solved by Simplex Method in polynomial time. For your information, Interior Point Method is the state-of-the-art for solving LP (and SDP). Ellipsoid Method theoretically works but is not practical.
Example 3 (Integer Factorization). Deciding if an integer is a prime is a problem in P, while the integer factorization problem is an NP problem: Given integers. Is there integer such that and divides . If the answer is Yes, then letting and does a number divide another number, one can verify the correctness in polynomial time. Clearly .
Example 4 (Partition Problem). This is a popular NP-complete problem: Given a sequence of positive integers. Is there such that ? We will come back to this thing when we discuss polynomial optimization.
Example 5 (Hamiltonian Cycle Problem). Given a graph . Does a Hamiltonian cycle exist? This is a problem in NP, and also known as NP-complete. We can also associate a counting problem to this problem: How many Hamiltonian cycles exist in the graph? We expect this problem is harder than checking the existence (NP).
Example 6 (Derangement Problem). This is a problem from the community of combinatorics. A derangement is a permutation (symmetric group) such that for all . Given a subgroup . Is there a derangement in ? This is known to be an NP-complete problem.
(Nov 15, 2013)
Next we define something called Turing reduction. Before that we need to allow the possibility for an algorithm to call subroutines (some black box processes). The academic name of subroutine is oracle.
Definition 8. An oracle is a pair where is a problem and is a polynomial such that for any instance , there exists such that and .
Also, we denote .
In words, we require in the oracle can be solved by some algorithm, but we have NO requirement on the running time or whatever about it (So it is really a black box). However, we need control on the length of the solution of .
Then we can define a Turing machine which is able to call oracles.
Definition 9. Let be a (-tape) Turing machine. An –oracle Turing machine is a -tuple such that:
(1) The last -tapes are called oracle tapes. Their heads are called oracle heads. The -th oracle tape has an oracle associated to it.
(2) The central unit is the superset of some .
(3) If the central unit is in the state , then the -th oracle tape is erased and miraculously replaced by some such that , for all .
As before, we can define the meaning of an oracle Turing machine solving a problem (just include the possibility of calling oracles).
(1) For any oracle Turing machine solving some problem, given an instance , we define to be the number of steps from the state to state , together with the number of times that oracles are called in between.
(2) The running time function of a oracle Turing machine solving some problem is given by:
(3) An oracle Turing machine solving some problem is polynomial when for any polynomials , there exists a polynomial such that for all .
(4) A Turing reduction from problem to is a polynomial 1-oracle Turing machine solving . A problem is said to be NP-easy if there exists such that can be Turing reduced to . A problem is said to be NP-hard if there is an NP-complete problem such that can be Turing reduced to .
Therefore NP-hard problems are harder than all NP problems. Examples include Traveling Salesman Problem (TSP) and Polynomial Optimization.
(Maybe the End, or more things coming)