5
$\begingroup$

Consider the class $\text{DLOGTIME}^{\text{ALL}}$: the class of problems that can be solved by a machine with unlimited computational power but only access to logarithmically many bits of the input. Which bits of the input it accesses can depend on the values of bits it has already seen, and it has random access to the input. For conciseness, let's call this language $\text{X}$.

Does this class have a name? What is known about it?

Here is what I know so far:

  • It includes problems that are very undecideable – it includes padded versions of every language whatsoever!
  • $\text{E}^\text{X} = \text{ALL}$ by a padding argument.
  • $\text{X}$ does not contain the problem $\text{PARITY}$ (are the number of 1 bits in the input even?). As such, $\text{X}$ does not contain the regular languages.

Questions:

  • Is $\text{X}$ contained in $\text{P}/\text{poly}$?
  • Is $\text{X}$ contained in any other well-known complexity class?
  • What else is known about $\text{X}$?
Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ "Does this class have a name?" -- you've given one. $\endgroup$ Commented Sep 22, 2016 at 6:56
  • $\begingroup$ Forgive me if this is a silly question, but how does an oracle for $ALL$ work exactly? I write my query, I enter the state $q_{query}$, and then? I cannot, in my query, identify the language I wish to query, because there are uncountably many. Is there an $ALL$-Complete language, and if not, which language does the oracle implement? $\endgroup$ Commented Sep 22, 2016 at 22:00
  • $\begingroup$ I briefly defined it in my answer. You write a real number to specify the language (on a write only tape), and consider this one step. I think this reflects what op intended. $\endgroup$ Commented Sep 23, 2016 at 10:07

1 Answer 1

Reset to default
3
$\begingroup$

It is contained in $P/Poly$

Let $M$ be a logarithmic time superoracle machine which decides some language $L$ in your class. We can define it by adding a special tape in which we can specify our desired language by writing some real number. Upon querying the oracle it will determine the membership of the given string to the specified language.

With polynomial length advice, you could provide the choice tree that determines what bits are read from a length $n$ input (if the first bit is x then go read y...). The questions to the oracles are determined by the bits read, and I can ask only a logarithmic number of questions (would work for polynomial too).

In the advice i could also hardcode a table which links any possible logarithmic input to the answers from the desired oracles. Given such advice and some input $x$, read the required bits using the choice tree, and simulate the special machine with the oracle answers given in the advice.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It seems that this shows something stronger (containment in L/Poly) $\endgroup$ Commented Sep 22, 2016 at 23:33
  • $\begingroup$ Seems true. You could probably also strengthen your class to $L^{\text{ALL}}$, just make sure oracle questions have to be written on a separate tape. $\endgroup$ Commented Sep 23, 2016 at 10:02

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.