13

You're right that the standard reduction from 3-SAT to 3D-matching (3DM) is not parsimonious. For the record, here's a sketch of a reduction that is parsimonious. It is obtained by composing parsimonious reductions from 3-SAT to 1-in-3-SAT, from 1-in-3-SAT to a problem we call 1+3DM, and from 1+3DM to 3DM. We sketch each of these next. Lemma 1. There is a ...


7

There are several #k-SAT algorithms in the literature which can beat $2^n$. Here is a randomized one that gets $2^{n(1-1/O(k))}$ time (like PPSZ): https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoMatthewsPaturi_2012_soda.pdf There is also a deterministic algorithm with $2^{n(1-1/O(k))}$ runtime behavior. Here is a link: http://tmc.web.engr.illinois....


7

The $\oplus P$-completeness of $\oplus$2SAT was resolved much earlier than Faben's preprint in 2008: it was resolved by Valiant himself in 2006. See Leslie G. Valiant: Accidental Algorithms. FOCS 2006: 509-517 https://ieeexplore.ieee.org/document/4031386 A link with no paywall: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.3342 Showing ...


5

Well one piece of evidence against PP being in BQP is that PP contains QMA, which is the NP equivalent of BQP.


3

The polynomial hierarchy would collapse to the fourth level (indeed, the third, see below). Proof. First, we get that $\oplus P\subseteq \Sigma_2^P$. This is because a $\Sigma_2^P$ machine can use its $\exists$ quantifier to guess a polynomial number of assignments and then, using its $\forall$ quantifier, verify that this list contains all of the formula's ...


2

I don't have a reference for you, just a minor remark that is too large for a comment. We assume $w$ is chosen as follows. Choose r.v. $x\in[0,1]^n$ uniformly at random (i.e., each $x_i$ is i.i.d. uniformly in $[0,1]$), then set $w_i = x_i/X$, where $X=\sum_j x_j$. Then with high probability, almost all sets $S$ will have $\sum_{i\in S} w_i \sim 1/2$: ...


2

Reading the discussion below the other answer made me realize that it’s not immediately obvious what is the complexity of translation of FO sentences in this language to equivalent FO1 sentences. While the quoted fact that satisfiability of these sentences is NEXP-complete (whereas satisfiability of FO1 sentences is in NP) implies that any such translation ...


2

Your (self) answer is ok, but you can also build a reduction in which there is no "trivial" solution. Start from $X = \{ x_{1}, \ldots, x_{n} \}, x_i > 0$ with target sum $K$ and build: $X' = \{ 8 * x_{1}, \ldots, 8 * x_{n} \} \cup \{ 1, 1, 2 \}$ and target sum $K' = 8*K + 2$ In this case in order to solve the new problem $\langle X', K' \...


1

This is #P-hard, already for an arbitrary fixed constant approximation factor. As you noted, it allows you to approximate $|f(x)|$ for any GapP-function $f$, and therefore if $f$ is any #P (or GapP) function, it allows you to approximate $|f(x)-y|$ for a given $y$. With this, you can still compute $f(x)$ by a form of binary search. Specifically, fix a ...


1

Yes, this appears to be true in the case that the integers are all positive. We simply take a Subset Sum instance defined by the set $ X = \{ x_{1}, \ldots, x_{n} \} $ and the target value $ K $ and create the set $ X' = X + \{ K \} $. Then there are at least two solutions to this problem if there is at least one to the original. Likewise, if there are two ...


1

Answering your second question, the logic you mean is known as Monadic FO or Monadic Predicate Calculus. It is known the logic is equivalent to FO1 (as Emil Jeřábek suggested) by some very old works by Behmann and Loewenheim. Regarding the first question, I do not know what is the complexity of model enumeration, but satisfiability checking is NExpTime-...


1

The answer is no, assuming we interpret Condition 2 as follows: For every infinite sequence $X_1,X_2,\ldots$ with each $X_i$ in $[0,1]$, $$\lim_{n \to \infty} \frac{F(X_1,...,X_n,Y, n)}{N(X_1,...,X_n,Y,n)} = 1.$$ Lemma 1. No function $F$ that satisfies the above condition is continuous (much less differentiable) in every $X_i$. Proof. Fix any candidate ...


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