The Complexity of Problems Defined by Boolean Circuits
The Complexity of Problems Defined by Boolean Circuits
复制标题
布尔电路定义的问题的复杂性
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
L. Theoretische
中科院分区：
文献类型：
--
作者：
S. Reith;K. Wagner;L. Theoretische
本文研究了由布尔函数的任意有限基上带门的布尔电路所定义的基于电路的组合问题（如电路值问题和可满足性问题）的复杂性。文献中对特殊病例进行了调查。我们给出了它们的复杂度随碱的完整表征。例如，对于带门的布尔电路的可满足性问题，我们给出了一个（可确定的）标准的完整集合，这些标准告诉我们这个问题在哪个条件下是完全的，是完全的，是完全的，是完全的，是完全的，或者是完全的。我们的证明充分利用了20年代由E.L. POST给出的布尔函数的所有闭类的表征。
We study the complexity of circuit-based combinatorial problems (e.g., the circuit value problem and the satisfiability problem) defined by boolean circuits w ith gates from an arbitrary finite base of boolean functions. Special cases have been investigated in the literature. We give a complete characterization of their complexity depending on the base . For example, for the satisfiability problem for boolean circuits with gates from we present a complete collection of (decidable) criteria which tell us for which this problem is in , is complete for , is complete for , is complete for , or is complete for . Our proofs make substantial use of the characterization of all closed classes of boolean functions given by E.L. POST already in the twenties.