3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ & wondering who 1st proved this & where.... $\endgroup$ – vzn Apr 17 '15 at 2:29

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.