1
$\begingroup$

Consider two problems as defined here.

Approximate counting: Given a Boolean function $f(x)$, for $x \in \{0, 1\}^{n}$, distinguish between the two cases:

  1. The number of satisfying assignments for $f(x)$ is $\geq 2^{k+1}$.
  2. The number of satisfying assignments for $f(x)$ is $\leq 2^{k}$.

We are promised that one of these cases is true. $k$ is some integer between $0$ and $n-1$.

Parity-SAT: Given a Boolean function $f(x)$, for $x \in \{0, 1\}^{n}$, output $1$ if the number of satisfying assignments to $f(x)$ is even.

Is there a way to reduce Parity-SAT to approximate counting (or vice versa)?

$\endgroup$
5
  • $\begingroup$ What's $k$? Part of the input? $n-1$? Please make the problem self-contained. $\endgroup$ – D.W. Mar 5 at 22:40
  • $\begingroup$ I suggest you read about en.wikipedia.org/wiki/PP_(complexity) vs en.wikipedia.org/wiki/Parity_P and read ahead in the notes. $\endgroup$ – D.W. Mar 5 at 22:43
  • $\begingroup$ I updated the question. The links you mention (or the lecture notes) do not contain a reduction $\endgroup$ – BlackHat18 Mar 6 at 3:55
  • $\begingroup$ Suppose the number of solutions is greater than $2^{k}$ but less than $2^{k+1}$? That would be a third case. $\endgroup$ – Kyle Jones Mar 12 at 22:54
  • $\begingroup$ We are promised that we are only in case 1 or case 2. $\endgroup$ – BlackHat18 Mar 14 at 15:13

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.