<p>Let <span class="math-container">$p(x)$</span> be a Boolean circuit on <span class="math-container">$n$</span> bits <span class="math-container">$x \in \{0,1\}^n$</span>.  Consider a program that computes a probability distribution over all sequences <span class="math-container">$x$</span>, autoregressively factored as
<span class="math-container">$$\pi(x | p) = \prod_{0 \le k \lt n} \pi(x_k | p, x_{&lt;k})$$</span>
That is, each <span class="math-container">$\pi(x_k | p, x_{&lt;k})$</span> is the output of a program which takes as input <span class="math-container">$p$</span> and <span class="math-container">$x_{&lt;k}$</span> and produces two probabilities summing to 1 for whether <span class="math-container">$x_k$</span> is 0 or 1.  I believe the following is true:</p>
<p><strong>Conjecture:</strong> There is no polynomial time <span class="math-container">$\pi$</span> s.t. for all circuits <span class="math-container">$p$</span> and all satisfying assignments <span class="math-container">$x$</span> and unsatisfying assignments <span class="math-container">$y$</span> of  <span class="math-container">$p$</span>, <span class="math-container">$\pi(x | p) &gt; \pi(y | p)$</span>.</p>
<p>Intuitively, the reason I believe this is that since conditional probabilities sum to 1 and the policy is causal (probabilities depend only the past), ensuring that satisfying assignments get high probabilities will require us to predict in advance whether a partial  assignment  is  likely  to  be  satisfying,  and  these  partial  predictions  are hard.  In particular, if one partial sequence <span class="math-container">$x_{&lt;k}$</span> gets at least as much probability as another <span class="math-container">$y_{&lt;k}$</span>, but all completions of <span class="math-container">$x_{&lt;k}$</span> are sat while all completions of <span class="math-container">$y_{&lt;k}$</span> are unsat, at least one pair of completions will violate the claim.</p>
<p>However, I haven't managed to turn this intuition into a proof, and regardless the claim has to be &quot;very close&quot;, since the uniform distribution satisfies the condition with <span class="math-container">$&gt;$</span> replaced with <span class="math-container">$\ge$</span>.  Moreover, the extreme case mentioned in the intuition is easy to rule out, simply by checking one particular completion.</p>
<p>I'm happy to assume a strong complexity class separation statement such as ETH or SETH to get the result if assuming <span class="math-container">$P \ne NP$</span> is insufficient.</p>

CC BY-SA 4.0
2020-11-11T21:59:28.430Z
Well, such $\pi$ exists at least for CNF. Let $\pi(x_1\ldots x_k)$ be proportional to the sum over $x_{k + 1} \ldots x_n$ of the number of clauses satisfied by $x_1 \ldots x_n$. We can compute $\pi(x_1\ldots x_k)$ in polynomial time, by computing the contribution of each clause independently.
Sasha Kozachinskiy
CC BY-SA 4.0
2020-11-12T09:29:29.843Z
Nice!  It does seem like the proportionality constant is computable too (in the same way), so that does work for the CNF case.
Geoffrey Irving
CC BY-SA 4.0
2020-11-12T09:54:48.297Z
Actually, does this work for all circuits as well, by converting to CNF and summing over the newly introduced variables as needed?
Geoffrey Irving
CC BY-SA 4.0
2020-11-12T10:04:39.550Z
Actually no, that doesn’t work, since if given $x_{<k}$ we don’t see the interleaved new variables.
Geoffrey Irving
<sat><pr.probability>
Can a tractable sequence distribution prefer satisfying to unsatisfying assignments?
Geoffrey Irving
# Can a tractable sequence distribution prefer satisfying to unsatisfying assignments?

(Asked by: username_0 on 2020-11-10)

Let $p(x)$ be a Boolean circuit on $n$ bits $x \in \{0,1\}^n$. Consider a program that computes a probability distribution over all sequences $x$, autoregressively factored as
$$\pi(x | p) = \prod\_{0 \le k \lt n} \pi(x\_k | p, x\_{
That is, each $\pi(x\_k | p, x\_{ is the output of a program which takes as input $p$ and $x\_{ and produces two probabilities summing to 1 for whether $x\_k$ is 0 or 1. I believe the following is true:

**Conjecture:** There is no polynomial time $\pi$ s.t. for all circuits $p$ and all satisfying assignments $x$ and unsatisfying assignments $y$ of $p$, $\pi(x | p) > \pi(y | p)$.

Intuitively, the reason I believe this is that since conditional probabilities sum to 1 and the policy is causal (probabilities depend only the past), ensuring that satisfying assignments get high probabilities will require us to predict in advance whether a partial assignment is likely to be satisfying, and these partial predictions are hard. In particular, if one partial sequence $x\_{ gets at least as much probability as another $y\_{, but all completions of $x\_{ are sat while all completions of $y\_{ are unsat, at least one pair of completions will violate the claim.

However, I haven't managed to turn this intuition into a proof, and regardless the claim has to be "very close", since the uniform distribution satisfies the condition with $>$ replaced with $\ge$. Moreover, the extreme case mentioned in the intuition is easy to rule out, simply by checking one particular completion.

I'm happy to assume a strong complexity class separation statement such as ETH or SETH to get the result if assuming $P \ne NP$ is insufficient.

**Tags:** sat, pr.probability

> **Comments:**
> **username_1**: Well, such $\pi$ exists at least for CNF. Let $\pi(x_1\ldots x_k)$ be proportional to the sum over $x_{k + 1} \ldots x_n$ of the number of clauses satisfied by $x_1 \ldots x_n$. We can compute $\pi(x_1\ldots x_k)$ in polynomial time, by computing the contribution of each clause independently.  
> **username_0**: Nice!  It does seem like the proportionality constant is computable too (in the same way), so that does work for the CNF case.  
> **username_0**: Actually, does this work for all circuits as well, by converting to CNF and summing over the newly introduced variables as needed?  
> **username_0**: Actually no, that doesn’t work, since if given $x_{<k}$ we don’t see the interleaved new variables.  

---

## 0 answers

