Generalized theorems on relationships among reducibility notions to certain complexity classes
From MaRDI portal
Publication:4298368
DOI10.1007/BF01578841zbMath0813.68105MaRDI QIDQ4298368
Publication date: 26 July 1994
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On the power of deterministic reductions to C=P ⋮ Relativized logspace and generalized quantifiers over finite ordered structures ⋮ A note on closeness between \(NP\)-hard sets and \(C_= P\) ⋮ Bounded queries to arbitrary sets
Cites Work
- Unnamed Item
- The strong exponential hierarchy collapses
- The complexity of computing the permanent
- Probabilistic polynomial time is closed under parity reductions
- The complexity of combinatorial problems with succinct input representation
- The complexity of optimization problems
- More complicated questions about maxima and minima, and some closures of NP
- Reductions on NP and p-selective sets
- A comparison of polynomial time reducibilities
- PP is closed under intersection
- PP is closed under truth-table reductions
- A complexity theory for feasible closure properties
- The difference and truth-table hierarchies for NP
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- On the power of deterministic reductions to C=P
- Relativization of questions about log space computability
- Computational Complexity of Probabilistic Turing Machines
- A relationship between difference hierarchies and relativized polynomial hierarchies
- The complexity of theorem-proving procedures
- On the power of parity polynomial time
- Counting classes: Thresholds, parity, mods, and fewness