11
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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). $\endgroup$ Apr 11 at 11:35
  • $\begingroup$ @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$. $\endgroup$ Apr 11 at 14:07
  • $\begingroup$ 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 $\endgroup$
    – D.W.
    Apr 13 at 6:07
  • $\begingroup$ To make the post more self-contained, can you give the definition of $H_i = \{ v : v\cdot w_i = 0 \}$? $\endgroup$
    – Neal Young
    Apr 13 at 15:11
  • $\begingroup$ @NealYoung Added! $\endgroup$ Apr 14 at 20:22

1 Answer 1

10
$\begingroup$

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.)


$\endgroup$
1
  • 1
    $\begingroup$ Thank you for your answer! $\endgroup$ Apr 14 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.