A taxonomy of problems with fast parallel algorithms

DOI10.1016/S0019-9958(85)80041-3MaRDI QIDQ3694688zbMATH OpenDBLPWikidataFDO

Authors Stephen Cook

Publication date 1985

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(85)80041-3

zbMATH Keywords

parallel greedy algorithmreducibilityuniform Boolean circuit families

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Recommendations

• scientific article; zbMATH DE number 4092771
• Paradigms for Fast Parallel Approximability
• scientific article; zbMATH DE number 3905850
• scientific article; zbMATH DE number 4068310
• scientific article; zbMATH DE number 4039280
• Paradigms for Fast Parallel Approximability
• Efficient parallel algorithms for parameterized problems
• scientific article; zbMATH DE number 4024789
• A complexity theory of efficient parallel algorithms
• scientific article; zbMATH DE number 4074482

Cited in

(only showing first 100 items - show all)

• Matching is as easy as matrix inversion
• Parallelism and the maximal path problem
• A parallel algorithm for the maximal path problem
• A parallel algorithm for bisection width in trees
• Parallel complexity of logical query programs
• A random NC algorithm for depth first search
• Membership testing in commutative transformation semigroups
• A parallelizable lexicographically first maximal edge-induced subgraph problem
• A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
• Parallel algorithms for solvable permutation groups
• Some subclasses of context-free languages in NC^ 1
• On a complexity hierarchy between L and NL
• A measure of relativized space which is faithful with respect to depth
• On a proposed divide-and-conquer minimal spanning tree algorithm
• Subtree isomorphism is NC reducible to bipartite perfect matching
• Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• The iterated mod problem
• Characterization of idempotent transformation monoids
• Programs over aperiodic monoids
• A new complete language for DSPACE(log n)
• The complexity of short two-person games
• Properties that characterize LOGCFL
• Arithmetizing uniform NC
• \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
• Circuits for computing the GCD of two polynomials over an algebraic number field
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• The complexity of computing the number of strings of given length in context-free languages
• Matrix inversion in RNC\(^ 1\)
• Characterizing parallel hierarchies by reducibilities
• A note on the space complexity of some decision problems for finite automata
• Oracle branching programs and Logspace versus \(P^*\)
• Highly parallel computations modulo a number having only small prime factors
• Perfect matching for regular graphs is AC^ 0-hard for the general matching problem
• The parallel complexity of finite-state automata problems
• Learning in parallel
• The complexity of circuit value and network stability
• Bounded arithmetic for NC, ALogTIME, L and NL
• Multiplication, division, and shift instructions in parallel random access machines
• The parallel complexity of coarsest set partition problems
• On iterated integer product
• Query languages for hierarchic databases
• Tight complexity bounds for term matching problems
• A very hard log-space counting class
• Extensions to Barrington's M-program model
• Unambiguity of circuits
• Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
• The computational complexity of pattern formation
• Sparse hard sets for P: Resolution of a conjecture of Hartmanis
• On deciding trace equivalences for processes
• Fast parallel constraint satisfaction
• Parallel solutions to geometric problems in the scan model of computation
• Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
• The complexity of computing maximal word functions
• Oracle computations in parallel numerical linear algebra
• A note on the complexity of deciding bisimilarity of normed unary processes
• A theory of strict P-completeness
• Space-efficient recognition of sparse self-reducible languages
• Implementing an ODE code on distributed memory computers
• An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
• On path equivalence of nondeterministic finite automata
• ALOGTIME and a conjecture of S. A. Cook
• Expressing uniformity via oracles
• On randomized versus deterministic computation
• Parallel evaluation of arithmetic circuits
• A query language for NC
• Nondeterministic stack register machines
• On the parallel complexity of loops
• The complexity of the characteristic and the minimal polynomial.
• Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.
• Reversible space equals deterministic space
• Inferring large graphs using \(\ell_1\)-penalized likelihood
• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
• Evaluation of circuits over nilpotent and polycyclic groups
• Weak theories of linear algebra
• Parallel graph algorithms that are efficients on average
• How hard is computing the edit distance?
• Computing a context-free grammar-generating series
• The proof complexity of linear algebra
• The complexity of planarity testing
• Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
• A note on logspace optimization
• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• Data independence of read, write, and control structures in PRAM computations
• String shuffle: circuits and graphs
• Resilient capacity-aware routing
• On the expressiveness of \textsc{Lara}: a proposal for unifying linear and relational algebra
• Equivalence classes and conditional hardness in massively parallel computations
• The model checking fingerprints of CTL operators
• On parallelizing a greedy heuristic for finding small dominant sets
• On approximating the eigenvalues of stochastic matrices in probabilistic logspace
• The enumerability of P collapses P to NC
• A note on some languages in uniform \(ACC^ 0\)
• An algebra and a logic for \(NC^ 1\)
• Inversion in finite fields using logarithmic depth
• Boolean circuits versus arithmetic circuits
• On uniformity within \(NC^ 1\)
• Ranking and formal power series
• Competitive self-stabilizing \(k\)-clustering
• Division in logspace-uniform NC

This page was built for publication: A taxonomy of problems with fast parallel algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3694688)