Monday, August 01, 2005

Relativizing Space

We normally define relativization to an oracle A with a special Turing machine that has an extra tape where the machine can write down a string x and move to a special state q? and will magically go to a state qy if x is in A and qn otherwise.

Scott Aaronson asked me about relativization for space classes noting the difficulty of the above definition. Does the oracle tape count as space? You want a log-space bounded machine to at least write its own input on the oracle tape but you don't want the tape to be used as auxiliary storage.

Ruzzo, Simon and Tompa developed the best model for oracle relativization. They allow a long oracle tape with the following restrictions:

  • The oracle tape is one-way write only.
  • A nondeterministic (or probabilistic or quantum) machine must act deterministically while writing on the oracle tape.
  • Once the query is made the tape is magically erased.
In this model a log-space machine can ask polynomial-size queries but these queries can be computed in log-space from the input and an extra O(log n) bits (the configuration of the machine right before writing the oracle query).

The Ruzzo-Simon-Tompa definition works well for defining Turing reductions for space-bounded machines but not so much for relativizing theorems, for example showing that alternating polynomial-time equals polynomial space for all oracles. Jonathan Buss gave a model to handle this case but we don't really get limitations on techniques for relativization results on space classes like we do for time. Best not even to bother looking for relativized space class oracles and just think of PSPACE of alternating polynomial-time in results like there is an A such that PA=PSPACEA.

3 comments:

  1. "You want a log-space bounded machine to at least write its own input on the oracle tape but you don't want the tape to be used as auxiliary storage."

    Given a witness on a read once certificate tape am I allowed to copy contents certificate to query?

    ---------

    Problem find x in g^x=h mod p.

    Read once certificate tape has witness x in binary.

    Assumption: g^{2^i x_i} mod p is in NC1 where x_i is ith bit.

    Cannot I scan the certificate tape from left to right and compute g^{2^i x_i} mod p accordingly and write to query tape and call a Logspace machine which does iterated multiplication which is in TC0 and calls another logspace machine to compute mod p?

    Similar strategy can place discrete logarithm in NL^i if modular exponentiation is in NC^i. Correct?

    ReplyDelete
  2. So modular exponentiation in nc implies discrete logarithm in quasiP? Does modular exponentiation in any o(n) space polytime algorithm have relation to natural proofs barrier?

    ReplyDelete
  3. "2. a nondeterministic (or probabilistic or quantum) machine must act deterministically while writing on the oracle tape."

    So copying from certificate tape is forbidden?

    Only copying from input tape is allowed?

    ReplyDelete