Self-Specifying Machines
| dc.creator | Hemaspaandra, Lane A. | |
| dc.creator | Hempel, Harald | |
| dc.creator | Wechsung, Gerd | |
| dc.date | 1999-10-01 | |
| dc.date.accessioned | 2026-07-07T03:24:23Z | |
| dc.date.available | 2026-07-07T03:24:23Z | |
| dc.description | We study the computational power of machines that specify their own acceptance types, and show that they accept exactly the languages that $\manyonesharp$-reduce to NP sets. A natural variant accepts exactly the languages that $\manyonesharp$-reduce to P sets. We show that these two classes coincide if and only if $\psone = \psnnoplusbigohone$, where the latter class denotes the sets acceptable via at most one question to $\sharpp$ followed by at most a constant number of questions to $\np$. | |
| dc.description | 15 pages, to appear in IJFCS | |
| dc.identifier | https://arxiv.org/abs/cs/9910006 | |
| dc.identifier | http://arxiv.org/abs/cs/9910006 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33305 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | Self-Specifying Machines | |
| dc.type | text |