Expressibility and Parallel Complexity
From MaRDI portal
Publication:4207580
DOI10.1137/0218043zbMath0688.68038WikidataQ61687225 ScholiaQ61687225MaRDI QIDQ4207580
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/4278570098b65d1a94598a05dd08fc95ce63c598
parallel RAM; first order expressibility; CRCW RAM; polynomial time hiearchy; uniformity of circuits
68Q25: Analysis of algorithms and problem complexity
Related Items
Some results on uniform arithmetic circuit complexity, Computational Power of Quantum Machines, Quantum Grammars and Feasible Computation, Reasoning and Query Answering in Description Logics, PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS, The descriptive complexity approach to LOGCFL, Model-checking hierarchical structures, The computational power of membrane systems under tight uniformity conditions, Low-complexity aggregation in GraphLog and Datalog, First-order logics: some characterizations and closure properties, The parallel complexity of two problems on concurrency, Reversal complexity revisited, Rudimentary reductions revisited, The invariant problem for binary string structures and the parallel complexity theory of queries, Capturing complexity classes by fragments of second-order logic, Diagonalization, uniformity, and fixed-point theorems, Reflective relational machines, A constant-space sequential model of computation for first-order logic, Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space, ALOGTIME and a conjecture of S. A. Cook, Circuits in bounded arithmetic. I, Recursion theoretic characterizations of complexity classes of counting functions, Reachability and the power of local ordering, Dyn-FO: A parallel, dynamic complexity class, A query language for NC, Nondeterministic stack register machines, Separating NC along the \(\delta\) axis, Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\), A note on some languages in uniform \(ACC^ 0\), On uniformity within \(NC^ 1\), Number of variables is equivalent to space, Extensions of an idea of McNaughton, Extensional Uniformity for Boolean Circuits, A Characterisation of NL Using Membrane Systems without Charges and Dissolution
