Logo image
Dual VP Classes
Accepted manuscript   Open access   Peer reviewed

Dual VP Classes

Eric Allender, Anna Gál and Ian Mertz
Lecture Notes in Computer Science, Vol.9235, pp.14-25
Milan (Italy), 2015
2015
DOI:
https://doi.org/10.7282/T3KK9DN4

Abstract

Arithmetic circuits Semiunbounded circuits Threshold circuits Algorithm analysis and problem complexity
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.
pdf
mfcsproc192.31 kBDownloadView
Accepted Manuscript (AM) Open Access
url
http://dx.doi.org/10.1007/978-3-662-48054-0View
Version of Record (VoR) Lecture Notes in Computer Science
url
Report an accessibility issueView
Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

Metrics

201 File downloads
92 Record Views

Details

Logo image