Self-Specifying Machines
classification
💻 cs.CC
keywords
setsexactlylanguagesmachinesmanyonesharpreduceacceptacceptable
read the original abstract
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$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.