scientific article; zbMATH DE number 3841223

MaRDI QIDQ3311653zbMATH OpenFDO

Authors Stephen Cook

Publication date 1983

zbMATH Keywords

fast parallel algorithmsparallel 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)

Cited in

(13)

• Fast parallel polynomial division via reduction to triangular Toeplitz matrix inversion and to polynomial inversion modulo a power
• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• Array processing machines: an abstract model
• Sequential and parallel complexity of approximate evaluation of polynomial zeros
• Complexity, combinatorial group theory and the language of palutators
• Chordal graph recognition is in NC
• On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
• Nondeterministics circuits, space complexity and quasigroups
• Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices
• On the parallel complexity of linear groups
• Parallel complexity of algebraic operations
• Catalytic computing and register programs beyond log-depth
• Application of contractor directions for solving systems of nonlinear equations

This page was built for publication:

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