A reminder: A polynomial reduction from one decision problem A to another decision problem B is a polynomial time algorithm that transforms valid INPUT from problem A to valid INPUT for problem B such that the answers A and B give to their respective input always match. At no time, do you actually have to solve Problems A or B; you're just transforming input from one to another. A problem A is NP-Complete if EVERY problem in NP can be reduced to problem A. A is NP-Complete if EVERY problem in NP can have its input transformed into valid input for A. (You're not transforming A's input. You're transforming everyone else's input to become input for problem A.) Cook's theorem is the proof that SATISFIABILITY is NP-Complete. Every single problem in NP was transformed into a logical expression that SATISFIABILITY requires so that SATISFIABILITY gives the same answer as the given NP problem on the given NP input. Any OTHER problem in NP can be proven NP-complete if you can reduce a known NP-complete to it. (You transform input FROM the known NP-Complete problem TO the problem you hope to prove to be NP-Complete.) If you can do this, then you know that your desired problem is NP-Complete: you can reduce the input from ANY NP problem to the known NP-complete problem in polynomial time...and THEN you can reduce THAT input to the new problem in polynomial problem: ANY NP Problem ==> Known NP-Complete Problem ==> Your problem Thus you can transform the input from ANY NP problem to input to your problem by using the known NP-Complete problem as a go-between. Let's say that you find a polynomial-time solution to ANY of the hundreds of known NP-Complete problems. You can then solve ANY problem in NP in polynomial time. You just reduce the problem (transform the input) to the problem you just solved. And then run your fast algorithm on the input given you by the reduction. ANY PROBLEM IN NP ==> The problem you just solved. Transform the input to your input (polynomial time) ==> Solve it (polynomial time) Thus, you can solve any problem in NP in polynomial time. So, if ANY of the NP-complete problems can be solved in polynomial time, then P=NP. So, is P likely to equal NP? Most people say no (including me): 1. There are hundreds of NP-Complete problems covering vast areas of mathematics and computer science, completely different from each other. Surely, someone would have solved just one of these problems quickly if it were possible to do so. 2. NP (nondeterministic) machines are VASTLY more powerful than actual machines. The most reasonable conclusion is that these powerful machines can more quickly solve a broad array of problems. However, some say yes: 1. The problems aren't COMPLETELY different from each other. They all have a similar kernel, which is why they can be reduced to each other. If someone sees a way to solve one, they'll probably see how to solve all of them; it wouldn't necessarily be a technique specific to graph theory, for example. 2. Just because no one's found one, that doesn't mean it exist. People have really only tried simple algorithm, n^2, n^3, etc. But these problems might well be solved with an N^100 or an n^1000 or an n^1000000 algorithm, which are much harder to visualize and construct. KNOWN NP-COMPLETE PROBLEMS: SATISFIABILITY. The "first one." 3SAT. Logical conjunctions of terms containing exactly three disjuncts. (a||b||c) && (d||e||f) && (!a || !e || g) && ... Is there a truth assignment to the variables that will make the logical statement true? This is different from SATISFIABILITY only in that we have we have exactly three disjuncts in each term. SATISFIABILITY has no limit. Two of the classic NP-Complete problems are graph problems. Graphs have edges and nodes. HAMILTONIAN CYCLE: Given a graph G = (V,E). Does the graph contain a Hamiltonian cycle? Meaning is there a way to follow the edges such that you can visit every point on the graph exactly once and then return to your starting point? So, like, if there are n vertices, is there a cycle of length exactly n that visits al lthe vertices? CLIQUE: A "clique" is a graph in which there is an edge between every two vertices. So a clique of size 2 has one edge. (Between the two vertices.) A clique of size 3 has three edges. (A<->B B<->C A<->C). A clique of size 4 has how many edges? Six. (A<->B B<->C C<->D A<->D A<->C B<->D). Like a square with an X connecting the corners. A clique of size 5 has how many edges? 10. If I have n nodes, each node connects to n-1 other nodes, so that's n(n-1), but I'm counting each edge twice this way A--> B is the same as B--> A, my answer is half that: n(n-1)/2 is the number of edges in a clique of size n. If I have 20 nodes, the number of edges in a clique is 20(19)/2 which is 190. The largest clique that is planar (meaning you can draw the graph on a flat sheet of paper without any of the edges crossing) is a clique of size 4. The CLIQUE problem is this. Given a graph G = (V,E) and an integer n, does the graph have a clique of size n? PARTITION: Given a collection of positive integers, can you split the collection into two collections of equal sum? SUBGRAPH ISOMORPHISM: Given two graphs G1 = (V1,E1) and G2 (V2,E2), does G2 contain a subgraph identical to G1? Can we find a correspondence between the vertices of V1 and SOME of the vertices of V2 such that if two vertices are connected in V1 their corresponding vertices in V2 are ALSO connected...and vice versa? We prove this NP-Complete by starting with a problem WE ALREADY KNOW is NP-Complete and transform the input from that known problem to input for our problem? Our known NP-Complete problem will be CLIQUE. CLIQUE ===> SUBGRAPH ISOMORPHISM Clique's input is a graph G = (V,E) and an integer n, representing the size of a clique. SUBGRAPH ISOMORPHISM's input is two graphs, G1 and G2. So, we are going to have transform Clique's input to SI's input. So, we have to transform a graph and an integer to two graphs. SI's G2 will be CLIQUE's G. This is just a copy job. SI's G1 will be a "complete graph" of size n. We will build a graph with n nodes with an edge between all pairs of nodes and that will be SI's G1. It will n^2 time to build such a graph, but n^2 is a polynomial and that's OK. But, let's say that G and n give a YES answer for CLIQUE. That means that graph G contains a clique of size n. Well, SI's G2 is the same as Clique's G which we known contains a clique of size n. And SI's G1 actually IS a clique of size n, so of course G1 contains G2 in it somewhere. Now let's say that SI's input gives a YES answer. That means that G2 contains a copy of G1 in it somewhere. But we specifically built G1 to be a clique of size n. So, G2 must contain a clique of size n. Since CLIQUE's G is the same as SI's G2, G also contains a CLIQUE of size n, so CLIQUE also has an answer of YES. The proof has to go in both directions. YES ==> YES YES <== YES totally valid. NO ==> NO NO <== NO totally valid. YES ==> YES NO ==> NO totally valid. YES ==> YES NO <== NO not valid, you loser. Notice that our reduction did not generate all possible valid inputs for SI. Our reduction ALWAYS made G1 a clique, but SI doesn't require G1 to be a clique. This is totally legal. Our reduction from A to B has to account for all valid inputs of A, but it does not have to hit all valid inputs of B.