Relativizing Function Classes
| dc.creator | Glaßer,Christian | |
| dc.creator | Wechsung,Gerd | |
| dc.date | 2003 | |
| dc.date.accessioned | 2024-02-06T12:52:13Z | |
| dc.date.available | 2024-02-06T12:52:13Z | |
| dc.description | The operators min?, max?, and #? translate classes of the polynomial-time hierarchy to function classes. Although the inclusion relationships between these function classes have been studied in depth, some questions concerning separations remained open. We provide oracle constructions that answer most of these open questions in the relativized case. As a typical instance for the type of results of this paper, we construct a relativized world where min_P #?NP, thus giving evidence for the hardness of proving min?P #?NP in the unrelativized case. The strongest results, proved in the paper, are the constructions of oracles D and E, such that min_coNPD #?PD NPD coNPD and UPE = NPE min?PE #?PE. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-009-01-0034 | |
| dc.identifier | https://lib.jucs.org/article/27926/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/8286 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 9(1): 34-50 | |
| dc.subject | polynomial-time hierarchy | |
| dc.subject | function classes | |
| dc.subject | oracle separations | |
| dc.title | Relativizing Function Classes | |
| dc.type | Research Article |