2
$\begingroup$

Consider the class $L^A$ which contains all the languages that are decided by a deterministic Turing Machine that uses $O(log(n))$ space and that can make queries to an oracle that decides $A$. My question is what is the length of query that the machine can ask the oracle? Is it $O(log(n))$ or can it be polynomial in $n$ (where $n$ is the length of the input)?

$\endgroup$
1
$\begingroup$

It seems that the usual definition, following Ruzzo, Simon and Tompa, is as follows. The oracle tape is write-only but has no space constraints. It is erased after each oracle call. In addition, if the machine model were non-deterministic (which is not your case), then the oracle calling process would have to be deterministic.

$\endgroup$

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.