scientific article; zbMATH DE number 784042

Walter L. Ruzzo, Raymond Greenlaw, H. James Hoover

Publication date: 13 August 1995

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

parallel random access machine circuit value problem \(P\)-complete problems generic machine simulation uniform Boolean circuit family

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Distributed algorithms (68W15)

Related Items (only showing first 100 items - show all)

The role of polymorphism in the characterisation of complexity by soft types ⋮ On the Average Case Complexity of Some P-complete Problems ⋮ The Logic of Choice ⋮ The Complexity of Small Universal Turing Machines: A Survey ⋮ On parallelizing a greedy heuristic for finding small dominant sets ⋮ Randomized OBDD-based graph algorithms ⋮ A mobility model for studying wireless communication and the complexity of problems in the model ⋮ On the universal and existential fragments of the \(\mu\)-calculus ⋮ On the complexity of generalized Q2R automaton ⋮ Parallel approximation algorithms for maximum weighted matching in general graphs ⋮ Equality Testing of Compressed Strings ⋮ Path Checking for MTL and TPTL over Data Words ⋮ Optimal edge ranking of trees in polynomial time ⋮ The complexity of linear programming in \((\gamma ,\kappa )\)-form ⋮ Constructing the highest degree subgraph for dense graphs is in \({\mathcal N}{\mathcal C}{\mathcal A}{\mathcal S}\) ⋮ On computational complexity of construction of c -optimal linear regression models over finite experimental domains ⋮ On regular realizability problems for context-free languages ⋮ SAT race 2015 ⋮ A PTIME-complete matching problem for SLP-compressed words ⋮ The parallel complexity of growth models ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Certified Graph View Maintenance with Regular Datalog ⋮ Crossing information in two-dimensional sandpiles ⋮ Rational index of languages with bounded dimension of parse trees ⋮ Unnamed Item ⋮ The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem ⋮ Predicting nonlinear cellular automata quickly by decomposing them into linear ones ⋮ Descriptive complexity of deterministic polylogarithmic time and space ⋮ A consequence of a proof of the one-way function existence for the problem of macroscopic superpositions ⋮ On the complexity of two-dimensional signed majority cellular automata ⋮ Complexity results for preference aggregation over \((m)\)CP-nets: max and rank voting ⋮ Partial order games ⋮ Modal Inclusion Logic: Being Lax is Simpler than Being Strict ⋮ Parallel Identity Testing for Skew Circuits with Big Powers and Applications ⋮ The complexity of the bootstraping percolation and other problems ⋮ Unnamed Item ⋮ A simple P-complete problem and its language-theoretic representations ⋮ Typechecking for XML transformers ⋮ PSPACE-completeness of majority automata networks ⋮ Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms. ⋮ On the Complexity of Equilibria Problems in Angel-Daemon Games ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ Parallelizing time with polynomial circuits ⋮ Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming ⋮ Graph coloring on coarse grained multicomputers ⋮ The computational complexity of generating random fractals ⋮ Two complexity results on \(c\)-optimality in experimental design ⋮ On the complexity of the stability problem of binary freezing totalistic cellular automata ⋮ The complexity of the asynchronous prediction of the majority automata ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ A second-order system for polytime reasoning based on Grädel's theorem. ⋮ Query languages for data exchange: beyond unions of conjunctive queries ⋮ Computational aspects of uncertainty profiles and angel-daemon games ⋮ Computational universality of fungal sandpile automata ⋮ Interval matrices with Monge property. ⋮ The complexity of game isomorphism ⋮ Lower bounds on the computational power of an optical model of computation ⋮ Dynamic Complexity of the Dyck Reachability ⋮ On short paths interdiction problems: Total and node-wise limited interdiction ⋮ A Characterisation of NL Using Membrane Systems without Charges and Dissolution ⋮ Computational complexity of threshold automata networks under different updating schemes ⋮ Hypercomputation by definition ⋮ Computing the minimal covering set ⋮ On the computational complexity of data flow analysis over finite bounded meet semilattices ⋮ Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ COLLAPSING THE HIERARCHY OF PARALLEL COMPUTATIONAL MODELS ⋮ Model Checking Games ⋮ Better complexity bounds for cost register automata ⋮ Unnamed Item ⋮ Queries and materialized views on probabilistic databases ⋮ The complexity of the majority rule on planar graphs ⋮ Parallel computation using active self-assembly ⋮ The computational power of membrane systems under tight uniformity conditions ⋮ The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions ⋮ Unnamed Item ⋮ Freezing sandpiles and Boolean threshold networks: equivalence and complexity ⋮ COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA ⋮ A randomized sublinear time parallel GCD algorithm for the EREW PRAM ⋮ On Computable Numbers, Nonuniversality, and the Genuine Power of Parallelism ⋮ Parallel identity testing for skew circuits with big powers and applications ⋮ The complexity of small universal Turing machines: A survey ⋮ The Complexity of Acyclic Subhypergraph Problems ⋮ Trace Refinement in Labelled Markov Decision Processes ⋮ On the complexity of asynchronous freezing cellular automata ⋮ The Parallel Complexity of Coloring Games ⋮ Cellular automaton growth on \(\mathbb{Z}^2\): Theorems, examples, and problems ⋮ Ideal membership in polynomial rings over the integers ⋮ Boolean circuit programming: A new paradigm to design parallel algorithms ⋮ The parallel complexity of approximating the high degree subgraph problem ⋮ The complexity of the comparator circuit value problem ⋮ Computing Prüfer codes efficiently in parallel ⋮ Circuits and expressions with nonassociative gates ⋮ Positive versions of polynomial time ⋮ The computational complexity of the Lorentz lattice gas ⋮ Optical computing ⋮ Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics ⋮ Decidability and complexity of simultaneous rigid E-unification with one variable and related results ⋮ On fungal automata ⋮ The enumerability of P collapses P to NC

This page was built for publication: