Stephen
Cook
University
of
Toronto
The P vs NP Problem
and
its
Place
in
Complexity
Theory
Abstract: We
present
an
historical
treatment
of
the
P
vs
NP
problems,
and
discuss
its
importance
and
approaches
for
solving
it.
We
relate
it
to
the
satifiability
problem
and
the
field
of
proof
complexity.