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)

Strict sequential P-completeness ⋮ Cellular automata universality revisited ⋮ Computational Complexity of Biased Diffusion-Limited Aggregation ⋮ Labeled shortest paths in digraphs with negative and positive edge weights ⋮ ReLU neural networks of polynomial size for exact maximum flow computation ⋮ The complexity gap in the static analysis of cache accesses grows if procedure calls are added ⋮ Various approaches to multiobjective linear programming problems with interval costs and interval weights ⋮ Unnamed Item ⋮ Reachability Switching Games ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ Parallel Computation Using Active Self-assembly ⋮ Logic, Languages, and Rules for Web Data Extraction and Reasoning over Data ⋮ Inverse Shortest Path Models Based on Fundamental Cycle Bases ⋮ Parallel algorithms for the maximum flow problem with minimum lot sizes ⋮ On the parallel approximability of a subclass of quadratic programming. ⋮ Graph Ramsey theory and the polynomial hierarchy ⋮ Tractable constraints in finite semilattices ⋮ Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets ⋮ A lower bound for the shortest path problem ⋮ Complexity thresholds in inclusion logic ⋮ On the Complexity of Value Iteration ⋮ Regular Realizability Problems and Context-Free Languages ⋮ Better complexity bounds for cost register automata ⋮ Natural complexity, computational complexity and depth ⋮ 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

This page was built for publication: