Characterizations of reduction classes modulo oracle conditions |
| |
Authors: | Ronald V Book Alan L Selman |
| |
Affiliation: | (1) Department of Mathematics, University of California at Santa Barbara, 93106 Santa Barbara, California, USA;(2) Department of Computer Science, Iowa State University, 50011 Ames, Iowa, USA |
| |
Abstract: | 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 polynomial space.This research was supported in part by the National Science Foundation under Grants MCS77-23493, MSC80-11979, MCS81-20263, and MCS83-12472. The work of the second author was also supported by the United States-Israel Educational Foundation (Fulbright Award). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|