NOTE: See also Notes on Unsolvability and Intractability
These problems can be described fairly simply. You might even think that you can come up with an equally simple algorithm. Unfortunately, it is unlikely that the algorithm you think of is both correct (not an estimate) and practical (in terms of time and space.)
An algorithm is different than a computer program that solves a particualar problem in that an algorithm is independent from a particular implementation or machine. For example, we talked about sorting algorithms without looking at C code. The algorithms we talked about could be implemented in any computer language on any type of computer. When we talk about the efficiency of an algorithm, we aren't talking about 10 seconds vs. 15 seconds. We're talking about theoretical running times, calculated in terms of the size of the input (usually.) Small, constant factors are ignored.
We've already seen the definitions for 'finite' and 'deterministic.' Make sure you understand them! Notice the wording for the effcient/inefficient definitions (in particular, 'some' vs. 'all'.)
All computers are capable of solving the same set of problems efficiently. The execution times and amounts of memory used will be different for the algorithms we can solve efficiently. BUT, for those problems which cannot be solved in polynomial time for all inputs, a better computer won't necessarily help. The traveling salesperson problem is an example of such a problem.
This slide provides some perspective in terms of concrete numbers and insight into the magnitude of the problem.
P: Polynomial algorithms - These include all the sorting algorithms we've seen, with running times on the order of nlgn and n2. Running times like n3 and 4, though considerably slower, are also polynomial time.
NP: Don't make the mistake of thinking that this class of algorithms is simply 'not polynomial.' The definition is a little more complicated than that. For this group of problems, no one has been able to find either a polynomial-time solution or a proof that none exists. For these problems, non-deterministic Turing machines can be constructed to solve them in polynomial time. Further, we can verify whether a given solution is correct for a NP problem in polynomial time. That means that if someone tells you the answer to the problem, you can write an algorithm to efficiently check whether or not it's the right one.
From the definitions of P and NP, you should be able to see that P is a subset of NP: any problem that can be solved deterministically in polynomial time can certainly be solved non-deterministically in polynomial time
In trying to understand the relation between 'lucky guessing' and non-determinism, recall the procedure for tracing through a n-FSA for a given input string to see whether it's accepted. When there were multiple arrows leaving a state for the same value, you had to randomly choose (guess.) Similarly, in the PDA example we've seen for testing whether a binary string is an even-length palindrome, you need to just 'magically know' when you've reached the half-way point in the string.
Basically, computer scientists have used computer theory to prove that some of the problems we want to solve are members of a group of problems called NP-Complete. A problem can be included in this group by proving its similarity to other problems in the group. By similarity, we mean that if one member of the group can be solved in polynomial time, we can translate the solution appropriately to solve any other problem in the group in polynomial time. So, this is a very important group. A solution for any of these problems that is polynomial proves that P=NP (not just P-NP-complete.)
The Satisfiability problem was mentioned in the first slide. Here's an example of the problem:
x = ((A+B)C)((ABC')+C)(ABC')
Can you assign boolean (true or false) values to each of A, B, and C so that x is true? If so, we say that the circuit is 'satisfiable.' This circuit (which could also be drawn with AND/OR/NOT gates) is unsatisfiable. (Make sure you review how to draw an AND/OR/NOT circuit from a boolean equation. You've usually seen the equations written with x, y, and z instead of A, B, and C.)
Let's go through the proof line by line
- We have this from our definition of NP.
- Recall how we can draw a FSA from a table of the states and input values. Similarly, when we describe a Turing machine, we do so in terms of its states and the actions we can take for a given input at each state. These rules can be used to encode a Turing machine. From this encoding, a logical formula can be written (trust me.)
- The result of this logical formula, true or false, corresponds to accept or reject. So, if we can solve this formula, we can solve the problem that the Turing machine encodes.
- The solution of the satisfiability problem can be translated back to a solution for the Turing machine - the values we get for each of the variables in the boolean formula correspond to the simulation of the Turing machine. This translation can be made in linear time.
- So, if we can solve the satisfiability problem in polynomial time, we'll be able to use this solution to find a solution to the problem encoded by the Turing machine, also in polynomial time.
By 'reducible,' we mean that a translation can be made between the problem and a boolean formula.
Most people don't believe that P=NP, because so many computer scientists have tried to solve so many of the problems in the NP-Complete group of problems that it's unlikely that they all weren't capable. So, once you prove that a problem is NP-Complete, conventional wisdom tells you to stop trying to solve the problem.
- We can hope to get lucky. Complexity theory deals with worst case running times. Maybe our algorithm runs quickly on many practical instances.
- In the Star Tours program, we used a heuristic to find a relatively good solution to the problem, one which took polynomial time.
- Sometimes, having 'unsolvable' problems is good. If we want to have a security code that can't be broken in a reasonable amount of time, we can use the property of NP-completeness. (Recall that we'll be able to verify whether a solution is correct in polynomial time.)