1
$\begingroup$

Let's assume we have an arbitrary language $L'$ and let's define the language $L = \{1^n | \text{The number of strings in } L' \text{ of length } n \text{ is odd }\}$.

Is $L\in PSPACE^{L'}$?

I tried saying that I can define a determinstic machine that holds a counter and that goes over all possible strings of length $n$, which is $2^n$, and for each such string it asks the oracle whether it is in $L'$. If yes it increases the counter, and if not, it does not. Then, at the end, checks if the counter is odd, and accepts if so. Else, it rejects.

The problem is that even in $PSPACE$ I can not go over all strings since that would not be a polynomial amount of space, except if I am allowed to override the previous string I checked and that would count only as $n$ space, but I am not sure..

Another part of the question asks if $L \in NP^{L'}$, but that clearly is not the case.

$\endgroup$
1
$\begingroup$

Yes it is, by exactly the argument you give. Looping over all possible strings of length $n$ requires only $n$ tape cells – you can do it by treating the length-$n$ strings as numbers in base $|\Sigma|$, so looping through those is essentially a counter, too. You can reuse the space since you don't care about strings that you've already tested. Testing if the string you just made is in $L'$ takes space $n$ on your oracle tape. Implementing the counter requires only $O(n)$ bits, since you only need to store a number in the range $0, \dots, |\Sigma|^n$. So the total amount of space required is linear in $n$.

In fact, you can do slightly better, though the total will still be $O(n)$ because of the need to loop through the length-$n$ strings. You don't need to count how many strings in $L'$ you've seen so far; you just need to know if that number is odd or even.

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