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


closed as unclear what you're asking by jmite, cody, Evil, David Richerby, Juho Sep 8 '15 at 8:48

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ 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. $\endgroup$ – David Richerby Sep 7 '15 at 14:45

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

  • 1
    $\begingroup$ There are also plenty of examples that are not in NP. (For your list, also sorting.) $\endgroup$ – 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).


Not the answer you're looking for? Browse other questions tagged or ask your own question.