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?

  • $\begingroup$ 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. $\endgroup$ – Marcos Villagra Aug 16 '10 at 22:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Aug 17 '10 at 2:25
  • $\begingroup$ @Marcos: I believe the answer is simply the resulting internal state of the machine, and is not written to the oracle tape. $\endgroup$ – Joe Fitzsimons Aug 17 '10 at 4:32
  • $\begingroup$ What is the reference for this definition of space-bounded oracle machines? $\endgroup$ – miforbes Aug 18 '10 at 6:13

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$.

  • 1
    $\begingroup$ 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). $\endgroup$ – miforbes Aug 18 '10 at 6:13
  • $\begingroup$ 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'$. $\endgroup$ – Arthur MILCHIOR Aug 24 '10 at 3:50

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


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.


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.