PSPACE, probabilistic-poly-time reduction

Question

A language $𝐿$ is in the class BPP if there exists a probabilistic polynomial- time TM, denoted N, such that: for every $𝛼 ∈ \{0,1\}^∗:$ $$𝛼 ∈ 𝐿 ⇒ Pr[𝑁(𝛼) = 1] ≥ 2 /3\\ 𝛼 ∉ 𝐿 ⇒ Pr[𝑁(𝛼) = 1] ≤ 1 /3.$$

We say that a language $𝐴$ has a probabilistic-poly-time reduction $𝑓$ to a language $𝐵$ if:

1. There exists a probabilistic polynomial time TM computing the (randomized) function $𝑓.$ Note that $𝑀(𝑥) = 𝑓(𝑥)$ is a random variable.

2. For all $𝑥 ∈ 𝐴$ it holds that $𝑃𝑟[𝑓(𝑥) ∈ 𝐵] >3/4.$

3. For all $𝑥 ∉ 𝐴$ it holds that $𝑃𝑟[𝑓(𝑥) ∉ 𝐵] >3/4.$

My question is, if a language $𝐴$ has a probabilistic-poly-time reduction to a language $𝐵$ and $𝐵 ∈ PSPACE$, then, is $𝐴 ∈ PSPACE?$ How to show that?

Answer 1

• PSPACE is the class of languages that can be decided by a deterministic Turing machine using polynomial space.

The goal is to show that if $B \in \text{PSPACE}$ , then $A \in \text{PSPACE}$.

Since $B \in \text{PSPACE}$ , there is a polynomial-space machine that can decide whether any given string belongs to $B$ . The probabilistic reduction $f(x)$ is computed in polynomial time, but we need to ensure that the probabilistic nature of the reduction can be handled within polynomial space.

Simulating Probabilistic Computation in PSPACE

The crucial insight is that a PSPACE machine has enough computational resources to try all possible random seeds used by the probabilistic reduction $f$ . Specifically, for a given input $x$ :

1. Compute all possible outcomes of $f(x)$ by simulating $f$ using every possible random choice.

   • Since $f$ is computed in probabilistic polynomial time, this means that for any fixed random seed, $f(x)$ can be evaluated in polynomial time. Therefore, the space used by $f(x)$ is still polynomial.

2. Count how many outcomes map to $B$:

   • The PSPACE machine can run the deterministic polynomial-space algorithm for $B$ on each possible outcome of $f(x)$ and count how many of these outcomes belong to $B$.

3. Decide membership in $A$ :

   • If more than $3/4$ of the possible outcomes of $f(x)$ belong to $B$ , conclude that $x \in A$.
   • If fewer than $1/4$ of the possible outcomes of $f(x)$ belong to $B$, conclude that $x \notin A$ .

Why This Works

Even though the reduction $f$ is probabilistic, the machine for $A$ can deterministically explore all random choices and simulate the behavior of $f(x)$ for each of them. Since $f(x)$ runs in polynomial time, this entire process uses polynomial space, as follows:

• The machine only needs polynomial space to store the current random seed, the output of $f(x)$ for that seed, and the result of checking whether the output belongs to $B$ .
• Because PSPACE machines can simulate polynomial-time probabilistic computations by trying all possible random seeds, this gives a deterministic PSPACE machine for $A$.

If $A$ has a probabilistic-poly-time reduction to a language $B$ and $B \in \text{PSPACE}$ , then $A \in \text{PSPACE}$ . The PSPACE machine can simulate all possible outcomes of the probabilistic reduction and decide $A$ deterministically within polynomial space.