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_{<k})$$ That is, each $\pi(x_k | p, x_{<k})$ is the output of a program which takes as input $p$ and $x_{<k}$ 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_{<k}$ gets at least as much probability as another $y_{<k}$, but all completions of $x_{<k}$ are sat while all completions of $y_{<k}$ 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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.