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.
>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.
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.