Characterization of reduction classes modulo oracle conditions

From MaRDI portal





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.











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)