The monotone and planar circuit value problems are log space complete for P
The monotone and planar circuit value problems are log space complete for P
复制标题
单调和平面电路值问题对于 P 来说是对数空间完备的
DOI：
10.1145/1008354.1008356
复制
发表时间：
1977
期刊：
影响因子：
--
通讯作者：
L. Goldschlager
中科院分区：
文献类型：
--
作者：
L. Goldschlager
Ladner [3]] 已经证明，电路值问题 (CV) 对于 P 来说是对数空间完备的，这又添加到了 Cook [iJ、Jones 和 Laaser [2] 发现的此类问题的列表中。拉德纳通过布尔电路对图灵机的模拟似乎需要一组“足够的”门，例如“与”和“非”。我们证明，仅使用“与”和“或”门的单调电路可以进行相同的模拟。定理 单调电路值问题（MCV）对于P 来说是对数空间完备的。证明显然MCV • P，并且下面的结构表明CV -<log MCV。所有定义如 E3]。令 o, -(°'l'''~m) 为电路，其中每个 c i 是变量 Xl,X2,...,x n 或门 AND (j,k) 或 NOT (j)，其中 j ~ k < i。令 ~ 为 ~, 变量的真值赋值。我们将使用单调电路来计算每个 ~ 的值。 i 及其否定值，如下。使用变量 Xl,X2,...~Xn,Xl,X2,...,x n 构建单调电路 @ = (@]...~2m) 使得 a) b)
Ladner [3] ]has shown that the circuit value problem (CV) is log space complete for P, adding to the list of such problems found by Cook [iJ and Jones and Laaser [2]. Ladner's simulation of Turing mac]hines by boolean circuits seems to require an "adequate" set of gates, such as AND and NOT. We show that the same simulation is possible with monotone circuits using AND and OR gates only. Theorem The monotone circuit value problem (MCV) is log space complete for P. Proof Clearly MCV • P, and the construction below shows that CV -<log MCV. All definitions are as in E3]. Let o, -(°'l'''~m) be a circuit where each c i is either a variable Xl,X2,...,x n or a gate AND (j,k) or NOT (j) where j ~ k < i. Let ~ be a truth assignment to the variables of ~,. We will use a monotone circuit to compute the value of each ~. i and the value of its negation, as follows. Construct a monotone circuit @ = (@]...~2m) with variables Xl,X2,...~Xn,Xl,X2,...,x n such that a) b)