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 .
an alternative definition (which i prefer) is given by arora's
a language is in if there exists a polynomial and a polynomial-time TM (called the verifier for ) such that if and satisfy , then we call a certificate for (with respect to the language and machine ).
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.
the following language is -complete: