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:
“The bed is now as public as the dinner table and governed by the same rules of formal confrontation.”
—Angela Carter (1940–1992)
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)