Characterization of reduction classes modulo oracle conditions
It is known that nondeterministic polynomial time truth-table reducibility is exactly the same as nondeterministic polynomial time Turing reducibility. Here we study the standard nondeterministic reducibilities (conjunctive, bounded truth-table, bounded positive truth- table, and many-one) and show that each is a restriction of nondeterministic polynomial time Turing reducibility corresponding to acceptance modulo a set of ``oracle conditions. Then we show that the reduction classes of these reducibilities are classes of formal languages and as such have language theoretic characterization theorems. The same program is carried out for polyomial space.
- 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
- 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
This page was built for publication: Characterization 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)