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.
dot - makes ``hierarchical'' or layered drawings of directed graphs. The layout algorithm aims edges in the same direction (top to bottom, or left to right) and then attempts to avoid edge crossings and reduce edge length.
neato and fdp - make ``spring model'' layouts. neato uses the Kamada-Kawai algorithm, which is equivalent to statistical multi-dimensional scaling. fdp implements the Fruchterman-Reingold heuristic including a multigrid solver that handles larger graphs and clustered undirected graphs.
I'm not entirely sure I see the value of this. Note that it doesn't tell us much about the state of the world, but rather more about the historical order in which these problems were inducted into the NP-completeness club. And by the time enough data points have been added to the picture to cover a meaningful fraction of the NP-complete problems that have been studied, will it even be possible to make sense of the humongous graph?
There are meaningful distinctions within NP-complete problems, such as whether they are easy to approximate. Perhaps if the graph incorporated that information, I can see this going somewhere..
It is incredibly useful for us kids just now learning about algorithms and trying to see if the problem described in the text book is reducible to a known NPC problem.
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.