# why is every self-reducible language in pspace

I understand that every self reducible language recursively queries its oracle with strings of length less than the input size. But how does that show that every such language can be solved in polynomial space?

You haven't defined self-reducible languages, so I'll take as an example SAT, and let you generalize the idea.

In order to solve SAT, we use the following recursive procedure:

1. If there are no variables, output the value of the formula.
2. Set the first variable to TRUE, and simplify the formula. Recurse. If TRUE is returned, return TRUE.
3. Set the first variable to FALSE, and simplify the formula. Recurse. If TRUE is returned, return TRUE.
4. Return FALSE.

When we set the first variable to TRUE, we need to keep a copy of the formula. At depth $k$ of the recursion, we have $k$ formulas, the size of each at most the size of the original formula. So for a formula of size $n$ having $m$ variables, the total space usage is $O(nm) = O(n^2)$, which is polynomial in the input size.

For general self-reducible languages the same technique applies, with similar results. The details depend on your notion of self-reducibility.

• & wondering who 1st proved this & where....
– vzn
Apr 17, 2015 at 2:29