The Algorithm Design Manual Second Edition

9.9

P vs. NP

The theory of NP-completeness rests on a foundation of rigorous but subtle defi-

nitions from automata and formal language theory. This terminology is typically

confusing to or misused by beginners who lack a mastery of these foundations.

It is not really essential to the practical aspects of designing and applying reduc-

tions. That said, the question “Is P=NP?” is the most profound open problem in

computer science, so any educated algorist should have some idea what the stakes

are.

9.9.1

Verification vs. Discovery

The primary question in P vs NP is whether verification is really an easier task

than initial discovery. Suppose that while taking an exam you “happen” to notice

the answer of the student next to you. Are you now better off? You wouldn’t dare

to turn it in without checking, since an able student such as yourself could answer

the question correctly if you took enough time to solve it. The issue is whether you

can really verify the answer faster than you could find it from scratch.

For the NP-complete decision problems we have studied here, the answer seems

obvious:

• Can you verify that a graph has a TSP tour of at most k weight given the

order of vertices on the tour? Sure. Just add up the weights of the edges on

the tour and show it is at most k. That is easier than finding the tour, isn’t

it?

• Can you verify that a given truth assignment represents a solution to a given

satisfiability problem? Sure. Just check each clause and make sure it contains

---

342

9 .

I N T R A C T A B L E P R O B L E M S A N D A P P R O X I M A T I O N A L G O R I T H M S

at least one true literal from the given truth assignment. That is easier than

finding the satisfying assignment, isn’t it?

• Can you verify that a graph G has a vertex cover of at most k vertices if given

the subset S of at most k vertices forming such a cover? Sure. Just traverse

each edge (u, v) of G, and check that either u or v is in S. That is easier than

finding the vertex cover, isn’t it?

At first glance, this seems obvious. The given solutions can be verified in linear

time for all three of these problems, while no algorithm faster than brute force

search is known to find the solutions for any of them. The catch is that we have no

rigorous lower bound proof that prevents the existence of fast algorithms to solve

these problems. Perhaps there are in fact polynomial algorithms (say O(n

7

)) that

we have just been too blind to see yet.