Difficult ProblemsPolynomial-time algorithmsNondeterministic algorithmsNondeterministic polynomial-time algorithmsFactoring large integersInteger bin packingBoolean satisfiabilityNP problems in generalMore NP problemsStill more NP problemsNP-complete problemsA famous questionWhy you should careThe EndDifficult ProblemsPolynomial-time algorithms•A polynomial-time algorithm is an algorithm whose running time is O(f(n)), where f(n) is a polynomial•A polynomial is an expression of the form:c0nk + c1nk-1 + c2nk-2 + ... + ck-1n + ck•An expression that has n as an exponent, such as 2n, is not a polynomial•For large enough values of n, 2n is larger than any polynomial, no matter what the coefficients or exponents may be•Exponential-time problems are said to be intractableNondeterministic algorithms•A nondeterministic computation is one which finds a solution regardless of the fact that it must make blind choices•A nondeterministic computation can be viewed in either of two ways: –When a choice point is reached, an infallible oracle can be consulted to determine the correct choice•Problem: There’s no such thing as an oracle–When a choice point is reached, all choices can be made and computation can proceed simultaneously•Problem: We don’t have computers with an infinite number of processorsNondeterministicpolynomial-time algorithms•A nondeterministic polynomial-time algorithm is an algorithm that can be executed in polynomial time on a nondeterministic machine•The machine can either consult an oracle (in constant time), or it can spawn an arbitrarily large number of parallel processes •It should be obvious that this would be a nice machine to haveFactoring large integers•Suppose you wish to factor a 100-bit integer•The smallest factor must be 50 bits or fewer•So you only need to try 250 (2n/2) factors–This is still exponential•Half of these potential factors are even, so you only need to try a single division by 2•So you only need to try 249 (2n/2-1) factors–This is still exponential•You can find many similar shortcuts, but it will still be exponential–There is no (known) polynomial-time algorithmInteger bin packing•Given a set of n positive integers, arrange them into two piles (bins), such that the sum of the integers in one pile is equal to the sum of the integers in the other pile. •For example, given these thirteen integers that sum to 1000:{19, 23, 32, 42, 50, 62, 77, 88, 89, 105, 114, 123, 176}can they be sorted into two bins that total 500 each? •Easy nondeterministic O(n) algorithm: Put each number in the correct bin–Remember, we have an oracle to tell us which bin is correct!•Another (but unfortunately exponential) algorithm: For all 13-bit numbers 0000000000000 to 1111111111111, try putting the corresponding integer into the first bin if the bit is a zero, the second bin if a oneBoolean satisfiability•Suppose you have:– n Boolean variables, A, B, C, ...–An expression in the propositional calculus (using and, or, and not operators)•Is there an assignment of truth values to the variables (such as A= true , B= true , C= false , ....) that will make the expression true ?•Here is a nondeterministic algorithm to solve the problem: For each Boolean variable, assign it the proper truth value. This is an O(n) algorithm•Exponential algorithm: Try all possible assignments of truth values to variablesNP problems in general•The preceding problems all had these characteristics in common:–There is a nondeterministic algorithm that solves the problem in polynomial time–Since we don’t have the mythical nondeterministic computer, the best known actual solution for each of these problems requires exponential time•It turns out that there are literally hundreds of similar NP problems•http://www.nada.kth.se/~viggo/problemlist/compendium.html is a good listMore NP problems•The travelling salesman problem –A salesman, starting in Harrisburg, wants to visit every capital city in the 48 continental United States, returning to Harrisburg as his last stop. In what order should he visit the capital cities so as to minimize the total distance travelled? •The Hamiltonian circuit problem –Every capital city has direct air flights to at least some other capital cities. Our intrepid salesman wants to visit all 48 capitals, and return to his starting point, taking only direct air flights. Can he find a path that lets him do this? •Equivalence of regular expressions –Do two distinct regular expressions represent the same language?Still more NP problems•Minimum graph coloring–Color the nodes of a graph, using the minimum number of colors, such that no two adjacent nodes are the same color•Graph isomorphism–Do two graphs have the same shape?•Minimum cover–Given some subsets of a set S, find a minimum number of those subsets such that every element of S is included•Longest substring–Given a set of strings, what is the longest substring that they have in common?NP-complete problems•All of the known NP problems have an amazing characteristic: they are all reducible to one another•This means that, given any two NP problems X and Y, –There exists a polynomial-time algorithm to restate a problem of type X as a problem of type Y, and –There exists a polynomial-time algorithm to translate a solution to a type Y problem back into a solution for the type X problem•In other words:–If you can find a polynomial-time algorithm for even one NP problem, you have found a polynomial-time algorithm for all of them•This is what the “complete” refers to when we talk about NP-complete problemsA famous question•Does P = NP? •No one has ever found a deterministic polynomial-time algorithm for any of the NP problems•No one has ever succeeded in proving that no such algorithm exists•The status for some years now is this: Most computer scientists don't think a polynomial-time algorithm can exist, but no one knows for sure. •This was a hot research topic for a while, but interest has died down on the problem, for the simple reason that no one has made any progress (in either direction)Why you should care•NP programs do not scale up–You can solve small problems of this type–You cannot solve medium or large problems•Someday you may well be asked to solve a problem of this type•It’s always a good idea to know what you can do and what you can’t do•It’s even more helpful to be able to