15.1 A Connecticut Class in King Arthur’s Court 241you really want to know, NP is the abbreviation ofNondeterministic Poly-
nomial Time, but it would be difficult to explain where this highly technical
phrase comes from). The two problems that Merlin had to face—the ex-
istence of a perfect matching and the existence of a Hamilton cycle—are
clearly NP properties. But NP properties also appear quite frequently in
other parts of mathematics. A very important NP property of natural num-
bers is theircompositeness: If a natural number is composite, then this can
be exhibited easily by showing a decompositionn=ab(a, b >1).
The remarks we have made so far explain how Merlin can remain free if
he is lucky and the task assigned to him by King Arthur has a solution. For
instance, suppose he could find a good way to seat the knights for dinner.
He could then convince King Arthur that his seating plan was “good” by
asking if there was anybody sitting beside any enemy of his (or just wait
and see if the dinner was quiet). This shows that the property of the cor-
responding “graph of friendships” that it contains a Hamilton cycle is an
NP property. But how could he survive Arthur’s wrath in the case of the
marriage problem and not in the case of the seating problem when these
problems donothave solutions? What distinguishes the nonexistence of a
Hamilton cycle in a graph from the nonexistence of a perfect matching in
a bipartite graph? From our tale, we hope the answer is clear:the nonexis-
tence of a perfect matching in a bipartite graph is also an NP property(this
is a main implication of the Marriage Theorem, Theorem 10.3.1), while the
nonexistence of a Hamilton cycle in a graph is not! (To be precise, no proof
of this latter fact is known, but there is strong evidence in favor of it.)
So for certain NP properties the negation of the property is again an NP
property. A theorem asserting the equivalence of an NP property with the
negation of another NP property is called agood characterization. There
are famous good characterizations throughout graph theory and elsewhere.
Many NP properties are even better. Facing the problem of marrying off
his knights and ladies, Arthur himself (say, after reading this book) could
decide himself whether or not it was solvable: He could run the algorithm
described in Section 10.4. A lot of work, but probably doable with the help
of quite ordinary people, without using the supernatural talents of Merlin.
Properties that can be decided efficiently are called propertiesin the class
P(here P stand forPolynomial Time, an exact but quite technical defi-
nition of the phrase “efficiently”). Many other simple properties of graphs
discussed in this book also belong to this class, such as connectivity and the
existence of a cycle. One of our favorite problems, that of deciding whether
a number is prime, was shown to be in this class just before our book went
to press. (The algorithm we described in Section 6.10 does not quite qualify
for the class P, because it uses a random selection of the basea.)
The introduction of the notions of Polynomial Time and NP properties
signaled the birth of modern complexity theory. Notions and paradigms
from this theory have penetrated a large part of mathematics and its ap-
plications. In the sequel we describe how ideas of complexity theory can be