21

In general, the query-tape for an oracle counts towards the space-complexity of a TM. However, it seems plausible to allow a write-only oracle-tape (such as is used in L-space reductions).

Is such a construction useful? Does it yield any particularly absurd results?

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Jeremy Hurwitz
  • 433
  • 3
  • 7
  • If you ave a TM with a write-only Oracle tape, how do you read the answer? You can just forget about the oracle then. – Marcos Villagra Aug 16 '10 at 22:54
  • 1
    There are delicate issues in deciding what is the right definition of oracle access for space-bounded machines. See "Relativizing Small Complexity Classes and their Theories" by Klaus Aehlig, Stephen Cook, and Phuong Nguyen, CSL 2007. – Kaveh Aug 17 '10 at 02:25
  • @Marcos: I believe the answer is simply the resulting internal state of the machine, and is not written to the oracle tape. – Joe Fitzsimons Aug 17 '10 at 04:32
  • What is the reference for this definition of space-bounded oracle machines? – miforbes Aug 18 '10 at 06:13

3 Answers3

10

I think one surprising fact is that in this model Savitch's theorem doesn't "obviously" relativize. That is, one can see that $PSPACE^P=EXPTIME$ and $NPSPACE^P=NEXPTIME$ in this model, and we don't currently know that $EXPTIME=NEXPTIME$ (and Savitch's theorem in this context does not seem to give it). I'd be interested in whether this can be pushed to "provably" non-relativizing.

One can also observe that $NL^{NL}=NL^L=NP$ in this model.

However, I think that this model is at least worth thinking about, with respect to issues of relativization in the space hierarchy theorem. Also, in some sense, I want $L^A$ to make poly-sized queries to $A$.

miforbes
  • 216
  • 1
  • 3
  • 1
    One thing I forgot: as NL=coNL we should want NL^NL=NL, but clearly if NL^NL=NP in this model we cannot use NL=coNL to collapse the "NL-hierachy". In a different notion of space-bounded oracles, the hierarchy does indeed collapse (see Immerman's NL=coNL paper for references). – miforbes Aug 18 '10 at 06:13
  • Do you have a reference ? I would have expected $\rm{NSPACE(0)^P=RE}$. Indeed, let $L$ be a language recursively enumerable, $M$ a TM who recognise $L$ and $M'$ a TM that read an input and a number $n$ of "1" and then simulates $M$ for this input on $n$ steps.

    Then without using any space I could copy the input on the oracle tape, guess the number of 1 needed and query $M'$.

     – Arthur MILCHIOR Aug 24 '10 at 03:50
9

This might not answer your question (which to be honest I don't fully understand), but I think it's in the same spirit. It's known that there is a difference in reducibility between a logspace TM with one oracle tape, and one with access to multiple oracle tapes. Also, the following notion of logspaceness has nice properties: the TM can only use a log-amount of space on its work tape, but it can use polynomial-amount of space on its oracle tapes.

Reference: http://groups.csail.mit.edu/tds/papers/Lynch/tcs78.pdf

Aaron Sterling
  • 6,994
  • 6
  • 42
  • 74
3

NSPACE(0)P=RE wich I guess is tad bit absurd.

Indeed, let L be a language recursively enumerable, M a TM who recognise L and M′ a TM that read an input and a number n of "1" and then simulates M for this input on n steps. Then without using any space I could copy the input on the oracle tape, guess the number of 1 needed and query M′.

Then, M' will accept iff M accept and have an input big enough to be polynomial.

Arthur MILCHIOR
  • 1,561
  • 10
  • 19