The final goal of research in complexity theory is to classify the complexity of real-world computational problems by providing lower bounds on the resources required to solve them. To date - in spite of impressive lower bounds for restricted types of circuits - almost the only useful progress toward this goal has come via the tool of reducibility which allows to show that a problem is complete for a complexity class. Thus the complexity class has become the fundamental object of study in complexity theory, and the basic questions in the field concern the relationships among complexity classes. Until these relationships are clarified, many important activities in computing ( in particular: public-key cryptography) will rest on uncertain conjectures. Many of the most important complexity classes can be characterized in terms of boolean circuits of restricted size or depth, etc. Recently, it has become apparent that arithmetic circuits are also very useful in this regard. The relationships between Booleau and arithmetric circuit complexity are still only poorly understood, although there has been significant progress on this front recently. This project will work to clarify these relationships further, and will seek to exploit the algebraic characteristics of arithmetic complexity classes to devise new approaches to prove lower bounds. Most of what we know about the complexity of real-world problems comes from the surprising fact that the overwhelming majority of such problems are complete for well-studied complexity classes, under very restrictive reducibilities. Recent progress has shown that these sets are actually isomorphic to each other, under very simple isomorphisms. Up to now, the work on isomorphisms has been primarily of theoretical interest. This project will work to see if the isomorphism theorems can be used to derive practical information about the complexity of real-world problems. More generally, this project will attempt to clarify the rel ationships among complexity classes, and the various notions (nondeterminism, unambiguity, symmetry, Boolean and arithmetic circuits, etc.) that define models of computation characterizing important complexity classes.
