Editing P (complexity) (section)

==Definition==
A [[Formal language|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 circuit]]s. A language ''L'' is in P if and only if there exists a [[Circuit complexity#Polynomial-time uniform|polynomial-time uniform]] family of Boolean circuits <math>\{C_n:n \in \mathbb{N}\}</math>, such that

* For all <math>n \in \mathbb{N}</math>, <math>C_n</math> takes ''n'' bits as input and outputs 1 bit
* For all ''x'' in ''L'', <math>C_{|x|}(x)=1</math>
* For all ''x'' not in ''L'', <math>C_{|x|}(x)=0</math>

The circuit definition can be weakened to use only a [[Circuit complexity#Logspace uniform|logspace uniform]] family without changing the complexity class.