The Algorithm Design Manual Second Edition

9.9.2

The Classes P and NP

Every well-defined algorithmic problem must have an asymptotically fastest-

possible algorithm solving it, as measured in the Big-Oh, worst-case sense of fastest.

We can think of the class P as an exclusive club for algorithmic problems that

a problem can only join after demonstrating that there exists a polynomial-time

algorithm to solve it. Shortest path, minimum spanning tree, and the original movie

scheduling problem are all members in good standing of this class P . The P stands

for polynomial-time.

A less-exclusive club welcomes all the algorithmic problems whose solutions can

be verified in polynomial-time. As shown above, this club contains traveling sales-

man, satisfiability, and vertex cover, none of which currently have the credentials

to join P . However, all the members of P get a free pass into this less exclusive

club. If you can solve the problem from scratch in polynomial time, you certainly

can verify a solution that fast: just solve it from scratch and see if the solution you

get is as good as the one you were given.

We call this less-exclusive club N P . You can think of this as standing for not-

necessarily polynomial-time

.

1

The $1,000,000 question is whether there are in fact problems in NP that cannot

be members of P. If no such problem exists, the classes must be the same and

P = N P . If even one such a problem exists, the two classes are different and

P

= NP . The opinion of most algorists and complexity theorists is that the classes

differ, meaning P

= NP , but a much stronger proof than “I can’t find a fast enough

algorithm” is needed.

1

In fact, it stands for nondeterministic polynomial-time. This is in the sense of nondeterministic automata,

if you happen to know about such things.

---

9 . 9

P V S . N P