3 ms·
I was wondering what the arrows actually mean. Turns out A->B means that A can be reduced to B (using a "polynomial-time many-one reduction"). So if we assume t
by wozer 18y ago
I was wondering what the arrows actually mean. Turns out A->B means that A can be reduced to B (using a "polynomial-time many-one reduction"). So if we assume that B is NP-complete, A is too.
So it all boils down to showing that Circuit Satisfiability is NP-complete.
I guess this graph shows the order in which the reductions were actually done for the first time.
When I was at college, we reduced everthing to 3-SAT and directly proved that 3-SAT is NP-complete, I think.
- mariorz 18y ago>Turns out A->B means that A can be reduced to B (using a "polynomial-time many-one reduction"). So if we assume that B is NP-complete, A is too. It's the other way around. For a given problem to be NP-complete requires that every problem in the NP superset be reducible to it in polynomial time. So in the A->B case, if we know A to be NP-complete, we have just proved every problem in NP is also reducible to B in polynomial time, by ways of any-NP-problem->A->B, ergo B is NP-complete.
- jacobscott 18y agoA well known quote (in the right circles): "Real men reduce from 3SAT" -- Christos Papadimitriou [http://www.cs.berkeley.edu/~christos/ http://www.cs.berkeley.edu/~christos/]
- shadytrees 18y agoI also wonder circuit satisfiability is tacked as a nexus in the graph. 3-SAT seems like a better choice due to Cook's theorem being such a big deal. http://en.wikipedia.org/wiki/Cook–Levin_theorem http://en.wikipedia.org/wiki/Cook–Levin_theorem