Equivalence Problems for Circuits over Sets of Natural Numbers |
| |
Authors: | Christian Glaßer Katrin Herr Christian Reitwießner Stephen Travers Matthias Waldherr |
| |
Affiliation: | 1. Julius-Maximilians-Universit?t Würzburg, Theoretische Informatik, Würzburg, Germany
|
| |
Abstract: | We investigate the complexity of equivalence problems for {∪,∩,−,+,×}-circuits computing sets of natural numbers. These problems were first introduced by Stockmeyer and Meyer (1973). We
continue this line of research and give a systematic characterization of the complexity of equivalence problems over sets
of natural numbers. Our work shows that equivalence problems capture a wide range of complexity classes like NL, C
=
L, P,Π2P, PSPACE, NEXP, and beyond. McKenzie and Wagner (2003) studied related membership problems for circuits over sets of natural numbers. Our results also have consequences for these membership problems: We provide an
improved upper bound for the case of {∪,∩,−,+,×}-circuits. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|