(soft question) Why are there so many NP-complete problems?

168 Views Asked by At

The definition of NP completeness feels very restrictive. For a language $L$ to be NP complete, everything in NP must reduce to it in polynomial time and yet it must still be in NP itself.

There is a Wikipedia article with a list of somewhere around 100 NP complete problems, all of which feel well-motivated by real-world problems: https://en.wikipedia.org/wiki/List_of_NP-complete_problems

In contrast, I am aware of a much smaller number of EXPTIME problems, such as generalized board games like chess and go. I am also aware of a much smaller number of problems not known to be in P but also not known to be NP hard, in fact the only major such problem that I know of is prime factorization.

Is there a reason why this is the case, or perhaps why NP completeness is not actually such a strong condition?

1

There are 1 best solutions below

0
On

Many combinatorial optimization problems (e.g., vertex cover, independent set) are "structurally" quite similar to each other, which makes reductions between them straightforward: you have exponentially many certificates to check, but if you can guess a good certificate you can verify YES instances quickly.

Now, once we have a few interesting combinatorial NP-Complete problems, we can "build" more combinatorial NP-Complete problems by reducing appropriately. For instance, say we have some graph-theoretic problem $\mathcal{P}$. It seems hard. It's not unreasonable, therefore, to think that we can thus reduce vertex cover or independent set to it in some clever way, because (a) those are also hard graph-theoretic problems and (b) typical graph theoretic problems tend to share a certain "structural" similarity which makes reductions between them amenable (unlike, say, Chess and Go).

One more point is that Boolean satisfiability, which is the original and canonical NP-Complete problem, somehow maps quite naturally to a wide array of graph-theoretic and combinatorial problems. If it wasn't for this fact, we might not have any NP-Complete problems except SAT! On the other hand, I don't think this can really be done with the known EXPTIME-Complete problems. What interesting problem can you possibly reduce Chess or Go to? Chess is just chess; Go is just Go. They don't seem particularly related to other problems (at least, not obviously).