Content deleted Content added
fix two broken refs |
The definition of logspace uniformity is not exactly correct; the definition in both Sipser and Arora & Barak use log-space transducers and not logarithmic space complexity which was implied |
||
Line 28:
===Logspace uniform===
A family of Boolean circuits <math>\{C_n:n \in \mathbb{N}\}</math> is ''logspace uniform'' if there exists a [[deterministic Turing machine]] ''M'', such that
* ''M'' runs in logarithmic work space (i.e. ''M'' is a [[log-space transducer]])
* For all <math>n \in \mathbb{N}</math>, ''M'' outputs a description of <math>C_n</math> on input <math>1^n</math>
| |||