Characterizations of reduction classes modulo oracle conditions

DOI10.1007/BF01744444zbMath0627.68042OpenAlexW1992316231MaRDI QIDQ3763590

Ronald V. Book, Selman, Alan L.

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

reduction classescomplexity classes of formal languagesnondeterministic reducibilitiesoracle conditionspolynomial time Turing reducibilitypolyomial space

Mathematics Subject Classification ID

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

Cites Work

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

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