EXPRESSIBILITY AND PARALLEL COMPLEXITY

作     者：IMMERMAN, N 

作者机构：Yale Univ CT United States 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1989年第18卷第3期

页      面：625-638页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：68025 computational complexity parallel complexity first-order expressibility polynomial-time hierarchy 

摘      要：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.