On the construction of parallel computers from various basis of Boolean functions

DOI10.1016/0304-3975(86)90165-9zbMath0604.68054OpenAlexW2094404282MaRDI QIDQ1083204

Leslie M. Goldschlager, Ian Parberry

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90165-9

zbMATH Keywords

parallel machinesparallel computationspace complexitycircuit value problemextended Turing machine

Mathematics Subject Classification ID

Related Items (32)

A complexity theory for feasible closure properties ⋮ On closure properties of GapP ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Counting Homomorphisms to Square-Free Graphs, Modulo 2 ⋮ Representing Boolean functions as polynomials modulo composite numbers ⋮ Relativized counting classes: Relations among thresholds, parity, and mods ⋮ Parallel computation with threshold functions ⋮ General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results ⋮ Unambiguous computations and locally definable acceptance types ⋮ Universally serializable computation ⋮ Locally definable acceptance types for polynomial time machines ⋮ Unnamed Item ⋮ On the power of generalized Mod-classes ⋮ Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes ⋮ Polynomial size \(\Omega\)-branching programs and their computational power ⋮ The consequences of eliminating NP solutions ⋮ On sets polynomially enumerable by iteration ⋮ THE THOMPSON–HIGMAN MONOIDS M_k,i: THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY ⋮ Strong self-reducibility precludes strong immunity ⋮ Modulo classes and logarithmic advice ⋮ The complexity of circuit value and network stability ⋮ Computing with discrete multi-valued neurons ⋮ On the power of parity polynomial time ⋮ Counting classes: Thresholds, parity, mods, and fewness ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ Lower bounds and the hardness of counting properties ⋮ Relating polynomial time to constant depth ⋮ The complexity of counting homomorphisms to cactus graphs modulo 2 ⋮ SELF-SPECIFYING MACHINES ⋮ Tally NP sets and easy census functions. ⋮ Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2 ⋮ Gap-definable counting classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A space efficient algorithm for the monotone planar circuit value problem
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Complete problems for deterministic polynomial time
• On the computational power of pushdown automata
• The Complexity of Enumeration and Reliability Problems
• Alternation
• A universal interconnection pattern for parallel computers
• Computational Work and Time on Finite Machines

This page was built for publication: On the construction of parallel computers from various basis of Boolean functions