An Introduction to Formal Languages and Automata, 7th Edition

14.7 NP-COMPLETENESS AND AN OPEN QUESTION

There are a number of problems that are central to complexity study and are such that, if we completely understood one of them, we would understand the major issue involved in tractability.

DEFINITION 14.4

A language L is said to be NP-complete if L ∈ NP and every L₁ ∈ NP is polynomial-time reducible to L.

It follows from this definition that if L is NP-complete and polynomial-time reducible to L₁, then L₁ is also NP-complete. So if we can find one deterministic polynomial-time algorithm for any NP-complete language, then every language in NP is also in P, that is,

$$P=NP.$$

Here we hold out the hope that efficient algorithms exist for such problems, even if none have been found yet. On the other hand, ...