The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers
The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers
复制标题
自然数集上的电路隶属问题的复杂性
DOI：
10.1007/s00037-007-0229-6
复制
发表时间：
2003
影响因子：
1.4
通讯作者：
K. Wagner
中科院分区：
文献类型：
--
作者：
P. McKenzie;K. Wagner
摘要：测试在{$$\bigcup，\bigcap，^-，+，\times $}组合电路的输出门处产生的自然数子集中的成员资格的问题被证明可以捕获广泛的复杂性类。虽然一般问题仍然是开放的，但案例{$$\bigcup，\bigcap，+，\times $$}显示为NEXPTIME-complete，案例{$$\bigcup，\bigcap，^-，\times $$}、{$$\bigcup，\bigcap，\times $$}、{$$\bigcup，\bigcap，+$$}显示为PSPACE-complete，案例{$$\bigcup，+$$}显示为NP-complete，案例{$$\bigcup，+$}显示为NP-complete，案例{$$\bigcup，+$}显示为NP-complete，案例{$\bigcap，^-，\times $}显示为PSPACE-complete，案例{$\bigcup，\times $$}显示为NP-complete，案例{$\bigcap，\times $$}显示为NP-complete，案例{$\bigcup +}被证明是C = L-完全的，并且解决了其他几种情况。有趣的辅助问题，如测试nonemptyness联合交叉级联电路，并表示每个整数，从一组给定的输入，作为权力的相对素数整数的一个选择。我们的结果在很大程度上扩展了Stockmeyer和Meyer（1973）、瓦格纳（1984）和Yang（2000）的工作。
Abstract.The problem of testing membership in the subset of the natural numbers produced at the output gate of a {$$\bigcup, \bigcap, ^-, +, \times$$} combinational circuit is shown to capture a wide range of complexity classes. Although the general problem remains open, the case {$$\bigcup, \bigcap, +, \times$$} is shown NEXPTIME-complete, the cases {$$\bigcup, \bigcap, ^-, \times$$ }, {$$\bigcup, \bigcap, \times$$}, {$$\bigcup, \bigcap, +$$} are shown PSPACE-complete, the case {$$\bigcup, +$$ } is shown NP-complete, the case {∩, +} is shown C=L-complete, and several other cases are resolved. Interesting auxiliary problems are used, such as testing nonemptyness for union-intersection-concatenation circuits, and expressing each integer, drawn from a set given as input, as powers of relatively prime integers of one’s choosing. Our results extend in nontrivial ways past work by Stockmeyer and Meyer (1973), Wagner (1984) and Yang (2000).