# Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

I have a question about the paper "NP is as easy as detecting unique solutions" by Valiant and Vazirani, specifically the proof of the Theorem 2.4(i).

The proof starts by saying

Clearly, $$P_n(S) \ge P(S) \cdot \Pr(H_1 \cap \ldots \cap H_n = \{ 0^n\})$$

Here, $$S \subseteq \{0, 1\}^n$$, $$P_n(S)$$ is defined as the probability over random vectors $$w_1, \ldots, w_n$$ that there is some $$i$$ between $$1$$ and $$n$$ such that $$|S_i| = 1$$ where $$S_i = \{v \in S : v \cdot w_1 = \cdots = v \cdot w_i = 0\}$$ where we take dot products mod 2. Also, $$H_i = \{ v \in \{0, 1\}^n : v \cdot w_i = 0 \}$$.

And $$P(S)$$ is defined to be the probability over infinite sequence $$w_1, \ldots$$ such that there is some $$i$$ such that $$|S_i| = 1$$.

Could anyone provide an explanation why the above statement is true?

We can show that the event $$\{ \exists i, \lvert S_i \rvert = 1 \& H_1 \cap \cdots \cap H_n = \{0^n\} \}$$ is contained in $$\{ \exists i \le n, \lvert S_i \rvert = 1 \}$$. So, it is sufficient to show that $$\Pr(\{ \exists i, \lvert S_i \rvert = 1 \& H_1 \cap \cdots \cap H_n = \{0^n\} \}) \ge P(S) P(H_1 \cap \cdots \cap H_n = \{0^n\})$$. This is equivalent to showing that $$\Pr(\{ \exists i, \lvert S_i \rvert = 1 \mid H_1 \cap \cdots \cap H_n = \{0^n\} \}) \ge P(S)$$.

My intuition is that the probability of the infinite sequence $$\lvert S_i \rvert$$ hitting to $$1$$ is independent of what happens to the sequence of $$H_1 \cap \cdots \cap H_k$$ for a fixed $$k$$, since with probability $$1$$, the intersection of $$H_i$$ will become $$\{0^n\}$$ at some point. But I am not really sure how to formalize this idea.

• Clearly, $P_n(S)\ge\Pr[\exists i\,|S_i|=1\& H_1\cap\dots\cap H_n=\{0\}]$. But it’s not clear to me why these two events should be independent (if that is intended to be the argument). Apr 11 at 11:35
• @EmilJeřábek That is as far as I got also. If we assume that $| S_i |$ becomes 1 at some point and $H_1 \cap \cdots \cap H_n = \{ 0^n \}$ then $S_i$ must have become singleton for some $i \le n$. I do not think those two events are independent, but it seems sufficient to show that they have a positive correlation. I am just not seeing it for the case when $0^n \notin S$. Apr 11 at 14:07
• Please don't use "EDIT: more stuff". Instead, revise the question so it reads well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755
– D.W.
Apr 13 at 6:07
• To make the post more self-contained, can you give the definition of $H_i = \{ v : v\cdot w_i = 0 \}$? Apr 13 at 15:11
• @NealYoung Added! Apr 14 at 20:22

For notational convenience define r.v.s

• $$T_S = \min\{i : |S_i| = 1\}$$ (recalling $$S_i = S \cap H_1 \cap \cdots \cap H_i$$), and
• $$T_H = \min\big\{i : H_1 \cap H_2 \cap \cdots \cap H_i = \{0^n\}\big\}$$.
1. Then $$P(S) = \Pr[T_S < \infty]$$ and $$P_n(S) = \Pr[T_S \le n]$$.

2. In all outcomes $$T_H \ge n$$ because $$|H_1 \cap \cdots \cap H_i| \ge 2^{n-i}$$, so $$T_H \le n$$ iff $$T_H = n$$.

3. It seems to me that the desired inequality can be shown as follows: \begin{align} P_n(S) & {} = \Pr[T_S \le n] &&(\textit{by the definitions}) \\ & {} \ge \Pr[T_S \le n ~~|~ T_H = n] ~\times~ \Pr[T_H = n] && (\textit{basic probability}) \\ & {} = \Pr[T_S < \infty ~|~ T_H = n] ~\times~ \Pr[T_H = n] && (\textit{see Step 10 below}) \\ & {} = \Pr[T_S < \infty] ~\times~ \Pr[T_H = n] && (\textit{see Step 20 below}) \\ & {} = P(S) ~\times~ \Pr[H_1 \cap H_2 \cap \cdots \cap H_n = \{0^n\}] && (\textit{by the definitions}) \end{align}

1. Next we argue that $$\Pr[T_S \le n ~|~ T_H = n]$$ equals $$\Pr[T_S < \infty ~|~ T_H = n]$$:

2. The event $$T_H = n$$ is equivalent to $$H_1 \cap H_2 \cap \cdots \cap H_n = \{0^n\}$$.

3. Given this event, $$H_1 \cap H_2 \cap \cdots \cap H_i = \{0^n\}$$ and $$S_i = S_n$$ for each $$i\ge n$$.

4. So (by the definitions) $$T_S \le n$$ iff $$T_S < \infty$$.

5. So $$\Pr[T_S \le n ~|~ T_H = n]$$ equals $$\Pr[T_S <\infty ~|~ T_H = n]$$, as desired.

1. Next we argue that $$\Pr[T_S < \infty ~|~ T_H = n]$$ equals $$\Pr[T_S < \infty]$$:

2. Call $$w_i$$ redundant if $$H_1 \cap \cdots \cap H_i = H_1 \cap \cdots\cap H_{i-1}$$.

3. If $$w_i$$ is redundant, then $$S_i = S_{i-1}$$, so, informally, the event $$T_S < \infty$$ is independent of redundant $$w_i$$'s.

4. Formally, consider modifying the random experiment so that redundant $$w_i$$'s are ignored. That is, redefine $$w_i$$ to be the $$i$$th non-redundant random vector. This does not change $$\Pr[T_S < \infty]$$.

5. But this modification is exactly the same as conditioning on $$T_H \le n$$, because each redundant vector doesn't change $$H_i$$, while each non-redundant vector cuts $$|H_i|$$ by a factor of two, so the distribution of first $$n$$ non-redundant vectors is exactly the same as the distribution of the first $$n$$ vectors conditioned on $$T_H \le n$$. (Out of time here, ask in comments if you have questions.)