What features of a problem make it NP-complete/hard?

Question

This isn't a question about what NP-completeness or hardness is, but about what, in general and informally, make a problem NP-complete? That is to say, what features of a problem might make me suspect a problem is NP-complete/hard?

To elaborate, for instance, lets say I’m seeing the graph coloring problem for the first time, or independent set, etc. Are there intrinsic features of these kinds of problems that might make me suspect they cannot be solved efficiently?

Answer 1

By definition, a problem is NP-complete if it's in NP and every other problem in NP can be reduced to it. The only literal answer to the question is that one: essentially, a problem is NP-complete only if it can be proven to be NP-complete. Since proof is a creative activity, it's not possible to give a series of rules, along the lines of "If a problem looks like X, Y or Z, then it's NP-complete."

However, there are some common features. First, the problem must be in NP, which means that we must be able to efficiently check a potential solution (e.g., check a proposed colouring for a colouring problem). Of course, designing efficient algorithms is also a creative act but, usually at least, proving that a new problem is in NP is fairly straightforward.

Once I've convinced myself that a problem is in NP, the thing that usually makes me feel that it might be NP-complete are non-locality and the presence of some kind of conflicting goals. Examples:

• Satisfiability problems are non-local in the sense that choices for the variables in one clause also affect many other clauses. There are competing goals in that clauses containing $X$ want us to make $X$ true, but clauses containing $\neg X$ want the opposite.
• In colouring problems, we wish to use as few colours as possible but features of the graph cause us to need many colours. Choices for colours in one part of the graph may have cause problems far away (see, e.g., Erdös's famous result that, for any $k$, there are graphs of arbitrarily large girth that are not $k$-colourable despite the fact that having large girth means they look locally like trees).
• In something like vertex cover, we're looking for a set that is, in a sense, "small but powerful". We can trivially find large vertex covers but the difficulty is in finding a small set that still does everything that we need.

Another feature can be that the "obvious" algorithm that you first think of seems to involve uncontrollable backtracking when you try to make it really work. For example, you might try to solve independent set greedily by starting with a single vertex and iteratively adding vertices that don't send any edges to the set you've built so far. But you soon realise that a bad choice early on can limit your options later and you start having to backtrack. Satisfiability problems tend to work like this, too.

However, be aware that adding even more restrictions to a problem can make it easier. For example, everything I've said above might make you suspect that 2-colourability and 2-SAT are NP-complete. But it turns out that 2-colourable graphs are so special that you can easily detect them and the back-tracking in 2-SAT can be kept under control.