<p>Blum, Shub and Smale created their model based on known algebraic models of computations, to unify (as much as possible) complexity theory and numerical analysis (<em>cf.</em> [1]). They wanted to give solid theoretical foundations to numerical analysis, and they wanted uniformity since the algorithms used in <em>real life</em> are uniform. Also, their model is a generalization of the Turing Machine, and having uniformity implies that $\mathsf {(N)P}_{\mathbb Z_2}$ in their model equals precisely $\mathsf{(N)P}$ in the classical model.</p>

<p>Uniformity is much less central for lower-bound questions, or as Bürgisser states it [2]:</p>

<blockquote>
  <p>Before, uniformity was not studied systematically in algebraic complexity, mainly because it is unknown how to exploit the uniformity condition for lower bound proofs.</p>
</blockquote>

<p>Note that non-uniformity in the BSS model can be studied also. This is the viewpoint taken for instance by Poizat [3].</p>

<p>As a final note, BSS model and Valiant's model have different goals, and I am not sure that uniformity is "preferable", neither that non-uniformity is preferable. As a argument for this, both models are used today to study different questions.</p>

<p><strong>References</strong></p>

<p>[1] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. "<a href="http://www.math.toronto.edu/shub/IJBC_0601.pdf">Complexity and real computation: A manifesto.</a>" International Journal of Bifurcation and Chaos 6, no. 01 (1996): 3-26.</p>

<p>[2] Peter Bürgisser. <a href="http://www-math.uni-paderborn.de/agpb/work/habil.pdf">Completeness and reduction in algebraic complexity theory</a>. Vol. 7. Springer, 2000.</p>

<p>[3] Bruno Poizat. Les petits cailloux: une approche modèle-théorique de l'algorithmie. Aléas, 1995.</p>

CC BY-SA 3.0
2014-01-23T10:27:18.810Z
I find your argument about $\mathbf{P}_{\mathbb Z_2}$ convincing.  I'll wait if other answers appear for a while and then accept your answer.
Pteromys
CC BY-SA 3.0
2014-01-23T09:32:17.220Z
2014-01-23T09:32:17.220Z
Bruno
<p>I understand that the study of Boolean circuits and nonuniform complexity classes was introduced to (hopefully) prove separation of uniform complexity classes.  In this sense, nonuniform computational models can be thought of as a secondary device in complexity theory, the main interest being the uniform model.</p>

<p>However, in algebraic complexity, the situation seems to have been the other way around.  Algebraic nonuniform models including algebraic circuits were studied long before the uniform Blum-Shub-Smale machines were introduced.  I am confused about this; since nonuniformity preceded uniformity in the algebraic setting, something about nonuniformity should have been unsatisfactory.  But what was wrong with straight-line programs?</p>

<p>I'd be grateful if you could tell me why uniformity in algebraic complexity theory can be preferable.</p>

<p>EDIT: I realized that uniformity helps if you are discussing <em>computability</em> of algebraic problems.</p>

<cc.complexity-theory><algebraic-complexity><arithmetic-circuits><computing-over-reals>
Uniformity vs. nonuniformity in algebraic complexity theory
Pteromys
# Uniformity vs. nonuniformity in algebraic complexity theory

(Asked by: username_0 on 2014-01-23)

I understand that the study of Boolean circuits and nonuniform complexity classes was introduced to (hopefully) prove separation of uniform complexity classes. In this sense, nonuniform computational models can be thought of as a secondary device in complexity theory, the main interest being the uniform model.

However, in algebraic complexity, the situation seems to have been the other way around. Algebraic nonuniform models including algebraic circuits were studied long before the uniform Blum-Shub-Smale machines were introduced. I am confused about this; since nonuniformity preceded uniformity in the algebraic setting, something about nonuniformity should have been unsatisfactory. But what was wrong with straight-line programs?

I'd be grateful if you could tell me why uniformity in algebraic complexity theory can be preferable.

EDIT: I realized that uniformity helps if you are discussing *computability* of algebraic problems.

**Tags:** cc.complexity-theory, algebraic-complexity, arithmetic-circuits, computing-over-reals


---

## 1 answers

### Answer by username_1 on 2014-01-23. Score: 11 | Accepted answer

Blum, Shub and Smale created their model based on known algebraic models of computations, to unify (as much as possible) complexity theory and numerical analysis (*cf.* [1]). They wanted to give solid theoretical foundations to numerical analysis, and they wanted uniformity since the algorithms used in *real life* are uniform. Also, their model is a generalization of the Turing Machine, and having uniformity implies that $\mathsf {(N)P}\_{\mathbb Z\_2}$ in their model equals precisely $\mathsf{(N)P}$ in the classical model.

Uniformity is much less central for lower-bound questions, or as Bürgisser states it [2]:

> Before, uniformity was not studied systematically in algebraic complexity, mainly because it is unknown how to exploit the uniformity condition for lower bound proofs.

Note that non-uniformity in the BSS model can be studied also. This is the viewpoint taken for instance by Poizat [3].

As a final note, BSS model and Valiant's model have different goals, and I am not sure that uniformity is "preferable", neither that non-uniformity is preferable. As a argument for this, both models are used today to study different questions.

**References**

[1] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. "[Complexity and real computation: A manifesto.](http://www.math.toronto.edu/shub/IJBC_0601.pdf)" International Journal of Bifurcation and Chaos 6, no. 01 (1996): 3-26.

[2] Peter Bürgisser. [Completeness and reduction in algebraic complexity theory](http://www-math.uni-paderborn.de/agpb/work/habil.pdf). Vol. 7. Springer, 2000.

[3] username_1 Poizat. Les petits cailloux: une approche modèle-théorique de l'algorithmie. Aléas, 1995.

> **Comments:**
> **username_0**: I find your argument about $\mathbf{P}_{\mathbb Z_2}$ convincing.  I'll wait if other answers appear for a while and then accept your answer.  

---

