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:
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)
“... 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)