Formal Definition
The complexity class NP can be defined in terms of NTIME as follows:
Alternatively, NP can be defined using deterministic Turing machines as verifiers. A language L is in NP if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that
- For all x and y, the machine M runs in time p(|x|) on input (x,y)
- For all x in L, there exists a string y of length q(|x|) such that M(x,y) = 1
- For all x not in L and all strings y of length q(|x|), M(x,y) = 0
Read more about this topic: NP (complexity)
Famous quotes containing the words formal and/or definition:
“True variety is in that plenitude of real and unexpected elements, in the branch charged with blue flowers thrusting itself, against all expectations, from the springtime hedge which seems already too full, while the purely formal imitation of variety ... is but void and uniformity, that is, that which is most opposed to variety....”
—Marcel Proust (1871–1922)
“The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)