Information Technology Reference
In-Depth Information
Chapter 4
Algebraic Complexity Classes
Meena Mahajan
Abstract
This survey describes, at an introductory level, the algebraic complexity
framework originally proposed by Leslie Valiant in 1979, and some of the insights
that have been obtained more recently.
·
·
·
·
Keywords
Algebraic complexity
Circuits
Formulas
Branching programs
·
Determinant
Permanent
·
Mathematics Subject Classification (2010)
Primary 68Q15
Secondary 68Q05
4.1 Introduction
In this survey, I am going to try and describe the algebraic complexity framework
originally proposed by Leslie and Valiant [
Va l 7 9
,
Va l 8 2
], and the insights that have
been obtained more recently. This entire article has an “as it appeals to me” flavour,
but I hope this flavour will also be interesting to many readers. The article is not
particularly in-depth, but it is an invitation to read [
BCS97
,
Bür00a
] and many recent
papers on the topic, and to start attacking the open problems in the area.
Valiant started out with themission of understanding the core essence of reductions
and completeness, as witnessed in both recursive function theory and in computa-
tional complexity theory. He provided an algebraic framework in which to interpret
the clustering of natural problems into completeness classes, even for problems of
an algebraic rather than combinatorial nature. He had a remarkable hypothesis:
The idea for writing this survey came while the author was working on the Indo-French
CEFIPRA-supported project 4702-1.
