New answers tagged

0

Take a look at the Cook Levin theorem, that shows a reduction from any $NP$ problem to $SAT$. Since $Dominating-Set\in NP$, this is a reduction $Dominating-Set\le_p SAT$. In the case I didn't understand your question and you wanted a reduction $SAT\le_p Dominating-Set$, consider creating the following graph: add a node for each variable $x_i$ and add another ...


3

If all clauses must be non-empty, then your problem isn't NP-hard, since every CNF can be half-satisfied: a random assignment satisfies at least half of the clauses in expectation, and so some assignment satisfies at least half of the clauses. If clauses are allowed to be empty (unsatisfiable), then there is an easy reduction from SAT: given an instance of ...


1

Yes, such an algorithm exists, but it is the same algorithm used for SAT solving in general. While the Tseytin extension variables associated with gates do appear in the CNF transformation of the original circuit, a minimally competent SAT solver will rarely branch on them. This is because one of the earliest heuristics discovered for speeding up searches ...


2

It is unknown whether the problem is $NP$-complete. In particular, you problem is non-trivial and it is in $P$. Therefore it is $NP$-complete if and only if $P=NP$. To see that your problem is in $P$ you can consider the following "brute-force" algorithm. Let $n$ be the number of variables and $n$ be the number of clauses. If it is possible to ...


0

If $x_7$ is a pure literal, then this means that you can satisfy all clauses containing $x_7$ by setting it to true. Accordingly, we set $x_7,x_5,x_6,x_8$ to true, satisfying all clauses apart from $\lnot x_2 \lor \lnot x_3 \lor x_4$, which we can satisfy by setting $x_4$ to true (for example). If you set $x_4,x_5,x_6,x_7,x_8$ to true, then the left-hand ...


4

No. This problem is equivalent to XOR-3SAT, in which we interpret each clause as $x \oplus y \oplus z$, where $\oplus$ is the XOR operator, and ask whether it's possible to find values for all variables so that each clause is true. XOR-SAT can be solved in polynomial time using Gaussian elimination, with all arithmetic done modulo 2 (i.e., in the finite ...


2

By Schafer's Dichotomy Theorem, if a clause is expressible as a system of linear equations over Zmod2, it is in P. Thus it would not be NP-Complete.


Top 50 recent answers are included