8
$\begingroup$

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.

$\endgroup$

1 Answer 1

11
$\begingroup$

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." International Journal of Bifurcation and Chaos 6, no. 01 (1996): 3-26.

[2] Peter Bürgisser. Completeness and reduction in algebraic complexity theory. Vol. 7. Springer, 2000.

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Pteromys
    Jan 23, 2014 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.