EXPRESSIBILITY AND PARALLEL COMPLEXITY
EXPRESSIBILITY AND PARALLEL COMPLEXITY
复制标题
DOI：
10.1137/0218043
复制
发表时间：
1989-06-01
影响因子：
1.6
通讯作者：
IMMERMAN, N
中科院分区：
文献类型：
--
作者：
IMMERMAN, N
它表明，所需的时间由一个并发读，并发写并行随机存取机（CRAM）检查输入是否有一定的属性是相同的最小深度的一阶归纳定义的属性。这反过来又等于“迭代”的一阶句子需要表达的财产的数量。本文的第二个贡献是引进一个纯粹的语法一致性的概念电路。本文证明了用一阶句子的“迭代“次数给出统一电路类的一个等价定义。类似地，uniform被定义为一阶可表达的性质（根据我们的主要定理，它反过来等于CRAM上的常数时间）。我们的主要结果的一个推论是一个新的特征的多项式时间层次（PH）：PH是等于一组接受的CRAM使用指数级的许多处理器和恒定的时间的语言。
It is shown that the time needed by a concurrent-read, concurrent-write parallel random access machine (CRAM) to check if an input has a certain property is the same as the minimal depth of a first-order inductive definition of the property. This in turn is equal to the number of “iterations” of a first-order sentence needed to express the property.The second contribution of this paper is the introduction of a purely syntactic uniformity notion for circuits. It is shown that an equivalent definition for the uniform circuit classesis given by first-order sentences “iterated”times. Similarly, uniformis defined to be the first-order expressible properties (which in turn is equal to constant time on a CRAM by our main theorem). A corollary of our main result is a new characterization of the Polynomial-Time Hierarchy (PH): PH is equal to the set of languages accepted by a CRAM using exponentially many processors and constant time.