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}$?
$\endgroup$
  • 1
    $\begingroup$ "Does this class have a name?" -- you've given one. $\endgroup$ – Raphael Sep 22 '16 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$ – Lieuwe Vinkhuijzen Sep 22 '16 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$ – Ariel Sep 23 '16 at 10:07
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.

$\endgroup$
  • $\begingroup$ It seems that this shows something stronger (containment in L/Poly) $\endgroup$ – Demi Sep 22 '16 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$ – Ariel Sep 23 '16 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.