Characterizing parallel hierarchies by reducibilities

DOI10.1016/0020-0190(91)90003-ZzbMath0741.68048WikidataQ127526121 ScholiaQ127526121MaRDI QIDQ1183416

Jian'er Chen

Publication date: 28 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

reducibilityoracle circuitsparallel complexity classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Parameterized Complexity and Subexponential-Time Computability ⋮ Strong computational lower bounds via parameterized complexity ⋮ Polynomial time approximation schemes and parameterized complexity ⋮ On log-time alternating Turing machines of alternation depth k ⋮ On input read-modes of alternating Turing machines ⋮ On the computational hardness based on linear fpt-reductions ⋮ Tight lower bounds for certain parameterized NP-hard problems

Cites Work

• On uniform circuit complexity
• The polynomial-time hierarchy
• On the Decomposability of $NC$ and $AC$
• A taxonomy of problems with fast parallel algorithms
• Two Applications of Inductive Counting for Complementation Problems
• Parallel computation and the NC hierarchy relativized
• Recursive Predicates and Quantifiers

This page was built for publication: Characterizing parallel hierarchies by reducibilities