Editing P versus NP problem (section)

===P and NP===
A ''decision problem'' is a problem that takes as input some [[String (computer science)|string]] ''w'' over an alphabet Σ, and outputs "yes" or "no". If there is an [[algorithm]] (say a [[Turing machine]], or a [[Computer programming|computer program]] with unbounded memory) that produces the correct answer for any input string of length ''n'' in at most ''cn<sup>k</sup>'' steps, where ''k'' and ''c'' are constants independent of the input string, then we say that the problem can be solved in ''polynomial time'' and we place it in the class P. Formally, P is the set of languages that can be decided by a deterministic polynomial-time Turing machine. Meaning,
:<math>\mathsf{P} = \{ L : L=L(M) \text{ for some deterministic polynomial-time Turing machine } M \}</math>
where
:<math>L(M) = \{ w\in\Sigma^{*}: M \text{ accepts } w \}</math>
and a deterministic polynomial-time Turing machine is a deterministic Turing machine ''M'' that satisfies two conditions:

# ''M'' halts on all inputs ''w'' and
# there exists <math>k \in N</math> such that <math>T_M(n)\in O(n^k)</math>, where ''O'' refers to the [[Big O notation#Formal definition|big O notation]] and
::<math>T_M(n) = \max\{ t_M(w) : w\in\Sigma^{*}, |w| = n \}</math>
::<math>t_M(w) = \text{ number of steps }M\text{ takes to halt on input }w.</math>

NP can be defined similarly using nondeterministic Turing machines (the traditional way). However, a modern approach uses the concept of ''[[Certificate (complexity)|certificate]]'' and ''verifier''. Formally, NP is the set of languages with a finite alphabet and verifier that runs in polynomial time. The following defines a "verifier":

Let ''L'' be a language over a finite alphabet, Σ.

''L'' ∈ NP if, and only if, there exists a binary relation <math>R\subset\Sigma^{*}\times\Sigma^{*}</math> and a positive integer ''k'' such that the following two conditions are satisfied:

# {{tooltip|2=For all strings x in Σ*, x is in L if and only if there is a y in Σ* such that (x, y) is in R and the length of y is polynomial in the length of x|1=For all <math>x\in\Sigma^{*}</math>, <math>x\in L \Leftrightarrow\exists y\in\Sigma^{*}</math> such that (''x'', ''y'') ∈ ''R'' and <math>|y|\in O(|x|^k)</math>}}; and
# the language {{tooltip|2=L[R], consisting of x followed by y with a delimiter in the middle"|1=<math>L_{R} = \{ x\# y:(x,y)\in R\}</math> over <math>\Sigma\cup\{\#\}</math>}} is decidable by a deterministic Turing machine in polynomial time.

A Turing machine that decides ''L<sub>R</sub>'' is called a ''verifier'' for ''L'' and a ''y'' such that (''x'', ''y'') ∈ ''R'' is called a ''certificate of membership'' of ''x'' in ''L''.

Not all verifiers must be polynomial-time. However, for ''L'' to be in NP, there must be a verifier that runs in polynomial time.

====Example====
Let
:<math>\mathrm{COMPOSITE} = \left \{x\in\mathbb{N} \mid x=pq \text{ for integers } p, q > 1 \right \}</math>
:<math>R = \left \{(x,y)\in\mathbb{N} \times\mathbb{N} \mid 1<y \leq \sqrt x \text{ and } y \text{ divides } x \right \}.</math>
Whether a value of ''x'' is [[Composite number|composite]] is equivalent to of whether ''x'' is a member of COMPOSITE. It can be shown that COMPOSITE ∈ NP by verifying that it satisfies the above definition (if we identify natural numbers with their binary representations).

COMPOSITE also happens to be in P, a fact demonstrated by the invention of the [[AKS primality test]].<ref name="Agrawal">{{cite journal |first1=Manindra |last1=Agrawal |first2=Neeraj |last2=Kayal |first3=Nitin |last3=Saxena |url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |archive-url=https://web.archive.org/web/20060926201057/http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |archive-date=2006-09-26 |url-status=live |title=PRIMES is in P |journal=[[Annals of Mathematics]] |volume=160 |year=2004 |issue=2 |pages=781–793 |doi=10.4007/annals.2004.160.781 |jstor=3597229 |doi-access=free }}</ref>