Definition
A language L is in P if and only if there exists a deterministic Turing machine M, such that
- M runs for polynomial time on all inputs
- For all x in L, M outputs 1
- For all x not in L, M outputs 0
P can also be viewed as a uniform family of boolean circuits. A language L is in P if and only if there exists a polynomial-time uniform family of boolean circuits, such that
- For all, takes n bits as input and outputs 1 bit
- For all x in L,
- For all x not in L,
The circuit definition can be weakened to use only a logspace uniform family without changing the complexity class.
Read more about this topic: P (complexity)
Famous quotes containing the word definition:
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)
“Was man made stupid to see his own stupidity?
Is God by definition indifferent, beyond us all?
Is the eternal truth man’s fighting soul
Wherein the Beast ravens in its own avidity?”
—Richard Eberhart (b. 1904)
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)