Generalized theorems on relationships among reducibility notions to certain complexity classes

DOI10.1007/BF01578841zbMath0813.68105MaRDI QIDQ4298368

Mitsunori Ogiwara

Publication date: 26 July 1994

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

reducibility

Mathematics Subject Classification ID

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