NP-complete - Common Misconceptions

Common Misconceptions

The following misconceptions are frequent.

• "NP-complete problems are the most difficult known problems." Since NP-complete problems are in NP, their running time is at most exponential. However, some problems provably require more time, for example Presburger arithmetic.
• "NP-complete problems are difficult because there are so many different solutions." On the one hand, there are many problems that have a solution space just as large, but can be solved in polynomial time (for example minimum spanning tree). On the other hand, there are NP-problems with at most one solution that are NP-hard under randomized polynomial-time reduction (see Valiant–Vazirani theorem).
• "Solving NP-complete problems requires exponential time." First, this would imply P ≠ NP, which is still an unsolved question. Further, some NP-complete problems actually have algorithms running in superpolynomial, but subexponential time. For example, the Independent set and Dominating set problems are NP-complete when restricted to planar graphs, but can be solved in subexponential time on planar graphs using the planar separator theorem.
• "All instances of an NP-complete problem are difficult." Often some instances, or even almost all instances, may be easy to solve within polynomial time.