Loading...
Please wait, while we are loading the content...
Expressibility And Parallel Complexity (1989)
| Content Provider | CiteSeerX |
|---|---|
| Author | Immerman, Neil Similarly, N. Times |
| Abstract | It is shown that the time needed by a concurrent-read, concurrentwrite parallel random access machine (CRAM) to check if an input has a certain property is the same as the minimal depth of a firstorder 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 classes AC i ; i 1 is given by first-order sentences "iterated" log i n times. Similarly, uniform AC 0 is 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. Key words. Computational c... |
| File Format | |
| Journal | SIAM J. of Comput |
| Publisher Date | 1989-01-01 |
| Access Restriction | Open |
| Subject Keyword | Syntactic Uniformity Notion First-order Sentence Equivalent Definition Polynomial-time Hierarchy Many Processor Parallel Complexity Uniform Circuit Concurrentwrite Parallel Random Access Machine First-order Expressible Property Minimal Depth Firstorder Inductive Definition |
| Content Type | Text |
| Resource Type | Article |
