# Are combinatorial problems inherently NP-Complete? [closed]

Most combinatorial problems seem NP-complete. Is this inherent in the design of the problems themselves? Are there any combinatorial problems in "P" ?

• What do you mean by "combinatorial problem"? There are plenty of problems in P and many of them, such as finding matchings, have a very combinatorial flavour. – David Richerby Sep 7 '15 at 14:45

No. Counterexamples (problems in $P$) include shortest path, max flow, minimum spanning tree,...

• There are also plenty of examples that are not in NP. (For your list, also sorting.) – Raphael Sep 7 '15 at 17:39

The "P" part of "NP" refers to the time on a nondeterministic TM being polynomial in the size of the representation of the input. This is an important point which sometimes gets lost when thinking about complexity theory.

One interesting consequence of this definition is that you can sometimes construct a problem in a higher complexity class by using a representation which is smaller.

Take any NP-complete problem using a "natural" representation, such as Hamiltonian circuit on a graph represented as an adjacency matrix. Note that the size of the representation of the graph is polynomial in $|V|$. Now let's suppose there is a compressed representation (e.g. a succinct circuit; I'll give a reference at the end) of the graph which is polylogarithmic in $|V|$, that is, a polynomial in $\log |V|$.

The compressed representation of the graph is exponentially smaller than the uncompressed representation. So any algorithm which solves the original problem on this input is exponentially more complex than an algorithm which solves the problem on the uncompressed representation! Specifically, the new problem is now NEXPTIME-complete which, by the time hierarchy theorem, is not in NP.

So to answer your question, no, combinatorial problems are not inherently NP-complete, because changing the representation of the input may change the complexity class of the problem. But in another sense they might be, because for a large class of problems, you may be able to choose a representation of the input which makes the problem NP-complete.

For more on succinct graphs and complexity theory: Galperin, Succinct Representations of Graphs, Information and Control, 56:183-198 (1983).