Characterizations of reduction classes modulo oracle conditions

DOI10.1007/BF01744444MaRDI QIDQ3763590zbMATH OpenOpenAlexFDO

Authors Ronald V. Book, Alan L. Selman

Publication date 1984

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

Full work available at URL https://doi.org/10.1007/bf01744444

zbMATH Keywords

complexity classes of formal languagesnondeterministic reducibilitiesoracle conditionspolynomial time Turing reducibilitypolyomial spacereduction classes

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1929453
• Algebraic characterizations for reduction systems
• Satisfiability and synthesis modulo oracles
• Reduction modulo sim and universality
• Orthogonality and Boolean Algebras for Deduction Modulo
• Characterizing polynomial complexity classes by reducibilities
• On the power of generalized Mod-classes
• On the mod \(p\) reduction of orthogonal representations
• scientific article; zbMATH DE number 3918383
• Random Oracle Reducibility

Cites work

• A comparison of polynomial time reducibilities
• Bounded query machines: on NP and PSPACE
• Bounded query machines: on NP( ) and NPQUERY( )
• On languages specified by relative acceptance
• Positive Relativizations of Complexity Classes
• Reductions on NP and p-selective sets
• Relationships between nondeterministic and deterministic tape complexities
• Reset machines
• Rudimentary Predicates and Relative Computation
• Simple Representations of Certain Classes of Languages
• Time- and tape-bounded Turing acceptors and AFLs

Cited in

(4)

• Decompositions of nondeterministic reductions
• scientific article; zbMATH DE number 3872715 (Why is no real title available?)
• Characterizing polynomial complexity classes by reducibilities
• Generalized theorems on relationships among reducibility notions to certain complexity classes

This page was built for publication: Characterizations of reduction classes modulo oracle conditions

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