Self-Specifying Machines

Hemaspaandra, Lane A.; Hempel, Harald; Wechsung, Gerd

Self-Specifying Machines

Authors

Hemaspaandra, Lane A.

Hempel, Harald

Wechsung, Gerd

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$.
15 pages, to appear in IJFCS