Graph of NP-Complete Problems

http://page.mi.fu-berlin.de/aneumann/npc.html

by imgabe • 17 years ago

54 7 17 years ago

page.mi.fu-berlin.de

andreyf• 17 years ago

For those wondering:

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.

source: http://www.graphviz.org/

wozer• 17 years 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• 17 years 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• 17 years ago

A well known quote (in the right circles):

"Real men reduce from 3SAT" -- Christos Papadimitriou [http://www.cs.berkeley.edu/~christos/]

shadytrees• 17 years ago

I 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

randomwalker• 17 years ago

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

Shamiq• 17 years ago

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.

Graph of NP-Complete Problems

Related Stories