Characterization of reduction classes modulo oracle conditions (Q3763590)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4020479
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Characterization of reduction classes modulo oracle conditions |
scientific article; zbMATH DE number 4020479 |
Statements
Characterizations of reduction classes modulo oracle conditions (English)
0 references
Characterization of reduction classes modulo oracle conditions (English)
0 references
1984
0 references
complexity classes of formal languages
0 references
nondeterministic reducibilities
0 references
polynomial time Turing reducibility
0 references
oracle conditions
0 references
reduction classes
0 references
polyomial space
0 references
0.84547305
0 references
0.8451758
0 references
0 references
0.8436373
0 references
0.8392811
0 references
0.83896124
0 references
0.8381712
0 references
0 references
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.
0 references