# Tag Info

8

Not necessary. Imagine the following Fake-#SAT problem: possible solutions are extended by one bit, and all vectors with this bit set are solutions. That is, the number of satisfying assignments for the new problem is $2^n+f$, where $f$ is the number of satisfying assignments for the original #SAT problem ($0\le f\le 2^n$). The problem remains #P-complete; ...

6

There is no such problem. If it's hard to sample, it's hard to integrate. Here is a sketch of the reason why. Represent every solution $x$ by a $n$-bit string $x_1,\dots,x_n$. If you can integrate over the set of all solutions, here is an algorithm to sample from all solutions: Count the number of solutions; call it $N_0$. (As you say, this can be done ...

3

I believe that the answer to your question is still no when $|Im(g)|$ is a constant fraction of $F_2^n$. Consider quadratic residues mod $N$. It is easy to generate them: Pick a random number $x$ mod $N$, and if $(x,N)=1$, then $x^2$ mod $N$ is a quadratic residue. But how can we generate quadratic non-residues? For this, we would need to find a quadratic ...

3

No. For example, if your input is a CNF with few solutions, then you can randomly generate non-satisfying assignment: just generate an assignment and keep it if it's non-satisfying. But generating a satisfying assignment is NP-hard.

2

No. Generating such strings is $NP$-Hard. Morally, this question is akin to, "is there an input $x$ to this machine which will make it output $y$?", and such questions are almost always $\text{(co)-NP}$-Complete. Our construction follows this line of thought, asking whether a machine which guesses an assignment to a CNF formula ever outputs Satisfiable''. ...

1

SHORT ANSWER: It is unknown whether $\mathsf{MAJ3CNF}$ is a $\mathsf{PP}$-complete problem under many-one reductions. LONG ANSWER: First of all, you refer to Bailey, Dalmau and Kolaitis, and their work on "Phase Transitions of $\mathsf{PP}$-complete Satisfiability Problems" in your question. Let me quote them: 'It is also worth noting that, although $\... 1 1) Yes, but only because of your definition. Take a unary language$L\in EXP\setminus BPP$(yeah, I know this might be empty, in that case just take something even bigger than$EXP$), that is very sparse in the sense that$n\notin L$if$n$is not a tower of$2's$, i.e., of the form$2^{2^{2^\ldots}}$. Define$p=\sum_{n\in L} 1/n$. This$p$is not$BPP\$-...

Only top voted, non community-wiki answers of a minimum length are eligible