# Can a tractable sequence distribution prefer satisfying to unsatisfying assignments?

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.

• 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. Nov 11, 2020 at 21:59
• Nice! It does seem like the proportionality constant is computable too (in the same way), so that does work for the CNF case. Nov 12, 2020 at 9:29
• Actually, does this work for all circuits as well, by converting to CNF and summing over the newly introduced variables as needed? Nov 12, 2020 at 9:54
• Actually no, that doesn’t work, since if given $x_{<k}$ we don’t see the interleaved new variables. Nov 12, 2020 at 10:04