polynomial time computability

an initial definition that i had studied was from davis'

a broken link: blk:def-lang $\text{[math]}$ an alphabet $\text{[math]}$ is said to be polynomial-time decidable if there is a turing machine $\text{[math]}$ that accepts $\text{[math]}$ , and a polynomial $\text{[math]}$ , such that the number of steps in an accepting computation by $\text{[math]}$ with input $\text{[math]}$ is $\text{[math]}$ . when the alphabet is understood, we write $\text{[math]}$ for the class of polynomial-time decidable languages.
[cite:;taken from @computability_davis_1994 chapter 15 polynomial-time complexity]

a total function $\text{[math]}$ on $\text{[math]}$ , where $\text{[math]}$ is an alphabet, is said to be polynomial-time computable if there is a turing machine $\text{[math]}$ that computes $\text{[math]}$ , and a polynomial $\text{[math]}$ , such that the number of steps in the computation by $\text{[math]}$ with input $\text{[math]}$ is $\text{[math]}$ .
[cite:;taken from @computability_davis_1994 chapter 15 polynomial-time complexity]

the following definition is the original definition of $\text{[math]}$ (based on the concept of a nondeterministic turing machine).

a language $\text{[math]}$ is said to belong to the class $\text{[math]}$ if there is a nondeterministic turing machine $\text{[math]}$ that accepts $\text{[math]}$ , and a polynomial $\text{[math]}$ , such that for each $\text{[math]}$ , there is an accepting computation $\text{[math]}$ by $\text{[math]}$ for $\text{[math]}$ with $\text{[math]}$ .
[cite:;taken from @computability_davis_1994 chapter 15 polynomial-time complexity]

an equivalent definition from arora's:

for every function $\text{[math]}$ and $\text{[math]}$ , we say that $\text{[math]}$ if there is a constant $\text{[math]}$ and a $\text{[math]}$ -time NDTM $\text{[math]}$ such that for every $\text{[math]}$ , $\text{[math]}$ .
[cite:;taken from @computability_arora_2009 definition 2.5]

another definition for $\text{[math]}$ (which i actually prefer):

a language $\text{[math]}$ is in $\text{[math]}$ if there exists a polynomial $\text{[math]}$ and a polynomial-time TM $\text{[math]}$ (called the verifier for $\text{[math]}$ ) such that for all $\text{[math]}$ :
$\text{[math]}$ if $\text{[math]}$ and $\text{[math]}$ satisfy $\text{[math]}$ , then we call $\text{[math]}$ a certificate for $\text{[math]}$ (with respect to the language $\text{[math]}$ and machine $\text{[math]}$ ).
[cite:;taken from @computability_arora_2009 definition 2.1]

we then have:

$\text{[math]}$ . if $\text{[math]}$ , then $\text{[math]}$ is recursive
[cite:;taken from @computability_davis_1994 chapter 15 polynomial-time complexity; theorem 2.3]

let
$\text{[math]}$ we show that the $\text{[math]}$ language defined in is in $\text{[math]}$ . recall that this language contains all pairs $\text{[math]}$ such that the graph $\text{[math]}$ has a subgraph of at least $\text{[math]}$ vertices with no edges between them (such a subgraph is called an independent set). consider the following polynomial-time algorithm $\text{[math]}$ : given a pair $\text{[math]}$ and a string $\text{[math]}$ , output $\text{[math]}$ if and only if $\text{[math]}$ encodes a list of $\text{[math]}$ vertices of $\text{[math]}$ such that there is no edge between any two members of the list. clearly, $\text{[math]}$ is in $\text{[math]}$ if and only if there exists a string $\text{[math]}$ such that $\text{[math]}$ and hence $\text{[math]}$ is in $\text{[math]}$ . the list $\text{[math]}$ of $\text{[math]}$ vertices forming the independent set in $\text{[math]}$ serves as the certificate that $\text{[math]}$ is in $\text{[math]}$ . note that if $\text{[math]}$ is the number of vertices in $\text{[math]}$ , then a list of $\text{[math]}$ vertices can be encoded using $\text{[math]}$ bits, where $\text{[math]}$ is the number of vertices in $\text{[math]}$ . thus, $\text{[math]}$ is a string of at most $\text{[math]}$ bits, which is polynomial in the size of the representation of $\text{[math]}$ .
[cite:;refer to @computability_arora_2009 chapter 2.1 the class np; example 2.2] gives an intuitive example of how the definition of $\text{[math]}$ relates to the "largest party you can throw" problem.
[cite:;taken from @computability_arora_2009 example 2.2]

$\text{[math]}$ .

let $\text{[math]}$ be languages, then we write
$\text{[math]}$ and say that $\text{[math]}$ is polynomial-time reducible to $\text{[math]}$ , if there is a polynomial-time computable function $\text{[math]}$ such that
$\text{[math]}$ [cite:;taken from @computability_davis_1994 chapter 15 polynomial-time complexity; theorem 2.3]

if $\text{[math]}$ and $\text{[math]}$ then $\text{[math]}$ is $\text{[math]}$ too. if $\text{[math]}$ and $\text{[math]}$ then $\text{[math]}$ is $\text{[math]}$ too.

a language $\text{[math]}$ is called $\text{[math]}$ -hard if for every $\text{[math]}$ , we have $\text{[math]}$ , $\text{[math]}$ is called $\text{[math]}$ -complete if $\text{[math]}$ and $\text{[math]}$ is $\text{[math]}$ -hard.
[cite:;taken from @computability_davis_1994 chapter 15 polynomial-time complexity; theorem 2.3]

$\text{[math]}$ is closed under intersection, broken link: blk:def-union and complementation.

$\text{[math]}$ is closed under broken link: blk:def-union and intersection.

if there is an $\text{[math]}$ -complete language in $\text{[math]}$ then $\text{[math]}$ .

the implications of $\text{[math]}$ are mind-boggling. $\text{[math]}$ problems seem to capture some aspects of "creativity" in problem solving, and such creativity could become accessible to computers if $\text{[math]}$ . 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 $\text{[math]}$ versus $\text{[math]}$ question is truly of great practical, scientific, and philosophical interest.
[cite:;taken from @computability_arora_2009 chapter 2.1 the class NP]

$\text{[math]}$ [cite:taken from @computability_arora_2009 definition 2.19]

the following language is $\text{[math]}$ -complete:
$\text{[math]}$ [cite:;taken from @computability_arora_2009 example 2.21]

for every $\text{[math]}$ , we say that $\text{[math]}$ if there exists a polynomial $\text{[math]}$ and a polynomial-time TM $\text{[math]}$ such that for every $\text{[math]}$ ,
$\text{[math]}$ note the use of the $\text{[math]}$ quantifier in this definition where polynomial_time_computability.html used $\text{[math]}$ .
[cite:;taken2 from @computability_arora_2009 definition 2.20]