Hacker News Reader

Comment by onos | Hacker News Reader

If there are counter examples, but they’re hard to find, this is still pretty interesting — it might meant we could say “most instances of an NP class of problem can be solved in P”.

View on HN

It is often the case that many instances of problems in NP are easy to solve. Take vertex 3-coloring - color the vertices of a graph with three different colors such that vertices connected by an edge have different colors. If your graph has only a few edges, then you can essentially color each vertex however you want as there are only a few constraints imposed by the few edges and in consequence there are many possible colorings. If your graph has many edges, then there is often only one way to color each vertex because of the constraints imposed by the many edges and in consequence there might only be one or a few possible colorings.

But somewhere in between too few and too many edges, there is a critical edge density where the problem undergoes a pretty rapid phase transition from essentially all colorings being valid to only very few colorings being possible and that is where the hard instances are mostly hiding.

We’ve known a less formal version of this for a long time though. People use SAT solvers because most of the time they work very quickly even though SAT is an NP problem.

You can also mix problems to change the average complexity. Take SAT (in NPC) and encode each instance with a word over a binary alphabet. Then add 2SAT (in POLY) and encode it using an alphabet with four letters. If you chose a random instance of length n, the probability it is from SAT is less than 1/2^n.

Still, this problem is NP complete, as it is in NP and you can trivially reduce SAT to it.

Reply on news.ycombinator.com