# Reduction between Parity-SAT and approximate counting

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

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