pith. sign in

arxiv: cs/9910006 · v1 · submitted 1999-10-01 · 💻 cs.CC

Self-Specifying Machines

classification 💻 cs.CC
keywords setsexactlylanguagesmachinesmanyonesharpreduceacceptacceptable
0
0 comments X
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.