TY - JOUR
TI - Dual VP Classes
DO - https://doi.org/doi:10.7282/T3KK9DN4
AU - Allender, Eric
AU - Gál, Anna
AU - Mertz, Ian
PY - 2015
T2 - Lecture Notes in Computer Science
VL -
IS -
SP - 14
EP - 25
AB - We consider the complexity class ACC^1 and related families of arithmetic circuits. We prove a variety of collapse results, showing several settings in which no loss of computational power results if fan-in of gates is severely restricted, as well as presenting a natural class of arithmetic circuits in which no expressive power is lost by severely restricting the algebraic degree of the circuits. These results tend to support a conjecture regarding the computational power of the complexity class VP over finite algebras, and they also highlight the significance of a class of arithmetic circuits that is in some sense dual to VP.
KW - Arithmetic circuits
KW - Semiunbounded circuits
KW - Threshold circuits
KW - Algorithm analysis and problem complexity
LA - English
ER -