On the Structure of Valiant's Complexity Classes
In Valiant developed an algebraic analogue of the theory of NP-completeness for computations of polynomials over a field. We further develop this theory in the spirit of structural complexity and obtain analogues of well-known results by Baker, Gill, and Solovay, Ladner, and Schöning.\par We show that if Valiant's hypothesis is true, then there is ...
