# Tag Info

0

We cannot deduce anything about the complexity of $g$. For a graph $G=(V,E)$, let $f_G$ be the function that maps each vertex set $S$ to $|S|$ if $S$ is an independent set and to $0$ otherwise. Obviously, $f_G$ is NP-hard to maximize. Now let $g_G$ be the function that maps each vertex set $S$ to $|V|$ if $S$ is nonempty and to $1$ if $S=\emptyset$. Then, ...

7

If $F_3$ and $F_2$ are both monotone, satisfiability can be checked in polynomial time (or even in coNLOGTIME), as $F_3\land F_2$, which is also monotone, is satisfiable iff it is satisfied by the $\vec1$ assignment, that is, iff it does not contain the empty clause. If one of the formulas is allowed to be monotone and the other one negated monotone (i.e., ...

12

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 ...

Top 50 recent answers are included