a language
an alphabet
is said to be polynomial-time decidable if there is a turing machine
that accepts
, and a polynomial
, such that the number of steps in an accepting computation by
with input
is
. when the alphabet is understood, we write
for the class of polynomial-time decidable languages.
a total function
on
, where
is an alphabet, is said to be polynomial-time computable if there is a turing machine
that computes
, and a polynomial
, such that the number of steps in the computation by
with input
is
.
a language
is said to belong to the class
if there is a nondeterministic turing machine
that accepts
, and a polynomial
, such that for each
, there is an accepting computation
by
for
with
.
we then have
. if
, then
is recursive
(refer to Boaz Barak and Sanjeev Arora, 2009 chapter 2.1 the class np example 2.2) gives an intuitive example of how the definition of
relates to the "largest party you can throw" problem.
.
let
be languages, then we write
and say that
is polynomial-time reducible to
, if there is a polynomial-time computable function
such that
if
and
then
is
too. if
and
then
is
too.
a language
is called
-hard if for every
, we have
,
is called
-complete if
and
is
-hard.
is closed under intersection, union and complementation.
is closed under union and intersection.
if there is an
-complete language in
then
.
the implications of
are mind-boggling.
problems seem to capture some aspects of "creativity" in problem solving, and such creativity could become accessible to computers if
. for instance, in this case computers would be able to quickly find proofs for every true mathematical statement for which a proof exists. resolving the
versus
question is truly of great practical, scientific, and philosophical interest.