Satisfiability of algebraic circuits over sets of natural numbers
Satisfiability of algebraic circuits over sets of natural numbers
复制标题
自然数集上代数电路的可满足性
DOI：
10.1016/j.dam.2010.04.001
复制
发表时间：
2007
影响因子：
0.5
通讯作者：
Matthias Waldherr
中科院分区：
文献类型：
--
作者：
Christian Glaßer;Christian Reitwießner;Stephen D. Travers;Matthias Waldherr
我们研究了计算自然数集的 {∪,∩,−,+,×} 电路可满足性问题的复杂性。这些问题是 Stockmeyer 和 Meyer (1973) [10] 以及 McKenzie 和 Wagner (2003) [8] 研究的表达式和电路隶属度问题的自然概括。我们的工作表明，可满足性问题涵盖了广泛的复杂性类别，例如 NL、P、NP、PSPACE 等。我们表明，在某些情况下，可满足性问题比成员资格问题更难。特别是，我们证明了测试 {∩,+,×}-电路的可满足性已经是不可判定的。与此相反，{∪,+,×}-电路的可满足性在 PSPACE 中是可判定的。
We investigate the complexity of satisfiability problems for {∪,∩,−,+,×}-circuits computing sets of natural numbers. These problems are a natural generalization of membership problems for expressions and circuits studied by Stockmeyer and Meyer (1973) [10] and McKenzie and Wagner (2003) [8]. Our work shows that satisfiability problems capture a wide range of complexity classes such as NL, P, NP, PSPACE, and beyond. We show that in several cases, satisfiability problems are harder than membership problems. In particular, we prove that testing satisfiability for {∩,+,×}-circuits is already undecidable. In contrast to this, the satisfiability for {∪,+,×}-circuits is decidable in PSPACE.