31
Technically, you can write $x\wedge \neg x$ in 3-CNF as $(x\vee x\vee x)\wedge (\neg x\vee \neg x\vee \neg x)$, but you probably want a "real" example.
In that case, a 3CNF formula needs at least 3 variables. Since each clause rules out exactly one assignment, that means you need at least $2^3=8$ clauses in order to have a non-satisfiable formula. Indeed, ...
20
The empty 3SAT instance (over no variables) has one solution.
16
If you are seeking a formula with 3 variables $x$, $y$, $z$, then you can consider clauses $(\ell_x \vee \ell_y \vee \ell_z)$ where $\ell_x$ is either $x$ or $\neg x$ (and same thing for $\ell_y$ and $\ell_z$). There is a total of 8 such clauses. If you consider a conjunction of all 8 clauses and remove exactly one of them, you get a 3-CNF formula with ...
15
The monotone version of X3SAT that your proof is based on has the nice property that setting a literal false in one clause will never cause the negation of that literal to be true in another, which means you can say
The only way a conflict can occur is when all literals in a clause are set to false.
and it will be true because forcing two literals false ...
14
$(3,k)\text{-LSAT}$ is in P for all $k$. As you have indicated, locality is a big obstruction to NP-completeness.
Here is a polynomial algorithm.
Input: $\phi\in (3,k)\text{-LSAT}$, $\phi=c_1\wedge c_2\cdots \wedge c_m$, where $c_i$ is the $i$-th clause.
Output: true if $\phi$ becomes 1 under some assignment of all variables.
Procedure:
Construct set $B_i$...
13
Try this:
$$
(A \lor B \lor C)
\land
(A \lor B \lor \lnot C)
\land
(A \lor \lnot B \lor C)
\land
(A \lor \lnot B \lor \lnot C)
\land
(\lnot A \lor B \lor C)
\land
(\lnot A \lor B \lor \lnot C)
\land
(\lnot A \lor \lnot B \lor C)
$$
11
$k$-SAT is defined as the problem of finding models (assignments of either true or false to the variables appearing in the formula) to propositional formulas in Conjunctive Normal Form (CNF). A clause is defined as a disjunction of literals (variables that are either in positive or negative form) and a CNF formula is then just a conjunction of clauses.
Thus,...
10
Here is one possible way to reduce Clique to SAT (you can then further reduce it to 3SAT). This type of reduction is often used in (propositional) proof complexity, an area of complexity theory.
Given a graph $G = (V,E)$ and a number $k$, we will have variables $x_{iv}$ for every $1 \leq i \leq k$ and every $v \in V$. You should think of $x_{iv}$ as stating ...
9
There is no conflict between your references. The problem is that they have slightly different definitions of what 3-SAT is. You need to read the (original) theorems by Tovey very carefully.
Let r,s-SAT denote the class of instances with exactly r variables per
clause and at most s occurrences per variable.
[...]
Theorem 2.1. Boolean ...
9
There is some research in this area. In The Effect of Restarts on the Efficiency of Clause Learning Jinbo Huang shows empirically that restarts improve a solver's performance over suites of both satisfiable and unsatisfiable SAT instances. The theoretical justification for the speedup is that in CDCL solvers a restart allows the search to benefit from ...
9
One variable: $(A \lor A \lor A)$
8
If you want more complex examples of such formulas, have a look some benchmark problems of SATLIB. ToughSAT is also a nice tool for creating 3-SAT instances; it's easy to build both satisfiable and unsatisfiable instances.
8
Research has concentrated not on the number of satisfying assignments, but on the clause density $\alpha$. It is (more or less) known that:
Below a certain threshold, the problem is easy. Moreover, the solution set is "continuous" (with high probability), in that all solutions are (more or less) connected.
After a certain threshold, there are no satisfying ...
7
The clauses are not intended to be equivalent, so you shouldn't call it an "equivalent representation in 3-literal clauses."
All the reduction requires is that the original formula has at least one satisfying assignment if, and only if, the new formula does. In this case, we have this property: if the original formula was satisfiable, we can choose at least ...
7
We can reduce 3SAT to ExactOneSAT (3SAT $\leq_P$ ExactOneSAT) as follows. Replace each clause $C_m$ by $(z_{m,1} \lor z_{m,2} \lor z_{m,3})$ and ensure that if $C_m$ is, say, $(v_i \lor \overline{v_j} \lor v_k)$ then $(\neg v_i \Rightarrow \neg z_{m,1})$, $(\neg \overline{v_j} \Rightarrow \neg z_{m,2})$ and $(\neg v_k \Rightarrow \neg z_{m,3})$. Thus, for ...
7
This is (sort of) a trick question. This is not about a connection between 2SAT and 3SAT, it is that if 3SAT is in P, then anything which is in NP and has at least one true instance and one false instance becomes NP-complete! Let's imagine that we are in a world where 3SAT is in P.
Now consider the simple problem 1-VAR-SAT, which is SAT where we have one ...
7
The random assignment algorithm can be derandomized (made deterministic) using the method of conditional expectations.
Let the 3SAT instance consist of clauses $C_1,\ldots,C_m$. During the algorithm we will assign values to variables. The score of a clause $C$ is defined as follows:
If $C$ is satisfied then its score is 1.
If $C$ is not satisfied and has $...
6
The statement
Formula $F$ is satisfiable $\iff$ graph has an independent set
is imprecise, since it does not specify which graph we are taling about. Correcting this, we get:
There is a polynomial-time function $\mathcal{G}$ from formulas to graphs such that, for all formulas $F$, $F$ is satisfiable $\iff$ $\mathcal{G}(F)$ has an independent set
...
6
Another way to put it:
2-SAT is in P and in NP.
if any problem in P (or in NP) is not NP complete, then P!=NP.
so if 2-SAT is not NP-complete, then P!=NP.
if P!=NP, then NP-complete problems are not in P.
so if 2-SAT is not NP-complete, then P!=NP and 3-SAT (being NP-complete) is not in P
equivalently (easier):
3-SAT is NP-complete.
if an NP-complete ...
6
The algorithm that decides 3-SAT just answers yes or no, satisfiable or not. It doesn't (directly) give you an assignment for the variables. You have to use the decision algorithm as a black box to find an assignment of the variables. You should try adding a something to your formula that lets you deduce the assignment of a particular variable without ...
6
There has been a lot of work on formalizing mathematics, and in all of this work one needs to express definitions, theorems and proofs within the logic that one is using for formalization.
This is always quite involved.
To describe the statement that 3SAT is NP-complete, we will need a version of first-order logic with a term language that will allow us ...
6
Yes, such a reduction exists. Subset Sum is NP-complete. FACT is in NP. Therefore, by the definition of NP-complete, there exists a reduction from FACT to Subset Sum.
To find such a reduction explicitly, work through the proof of NP-completeness for Subset Sum; it will describe such a reduction. (Implicitly, we get a reduction from FACT to SAT by Cook's ...
5
Grover's algorithm is already suitable. It promises that if there is at least one match, then it will output at least one match. It doesn't promise to output all matches, but you don't need all matches.
It is usually described to work in the case where there is zero or one items that match, but that's just because those are the hardest cases. If there ...
5
One way to show that SSUM is NP-hard is by reduction from SUBSET-SUM. The idea is to replace each number $n_i$ by two numbers $Mn_i + \epsilon_i$ and $\epsilon_i$, where $M$ is a "large" integer and $\epsilon_i$ is a "small" integer. By varying $\epsilon_i$ you ensure that all numbers are different. You set your target at $MT+\delta$, where $T$ is the ...
5
We went through this yesterday. The only property required for a reduction from 3SAT to 2SAT is that it maps satisfiable 3CNF formulas to satisfiable 2CNF formulas, and unsatisfiable 3CNF formulas to unsatisfiable 2CNF formulas. There is no other requirement. The formulas do not have to be related in any other way. They don't have to have the same truth ...
5
A CNF which is not satisfiable is usually called unsatisfiable. A CNF which is unsatisfiable but becomes satisfiable if we drop any clause is minimally unsatisfiable.
Papadimitrious and Wolfe constructed, in their paper The complexity of facets resolved (Lemma 1), a polynomial time reduction $f$ from CNFs to CNFs such that:
If $\varphi$ is satisfiable then $...
4
Main idea: For each variable $x_i$ introduce a new variable $y_i$ and add a new clause $(\lnot x_i, \lnot y_i)$. Replace each occurence of $\lnot x_i$ in the original clauses by $y_i$.
The new clauses ensure that $y_i$ can be set to true if and only if $x_i$ is false. Thus we neither add nor remove satisfying assignments for the original clauses, while the ...
4
Yes, going from 3SAT (also called 3CNFSAT) to CNFSAT (also called just SAT) is trivial. The function $f$ you are looking for is just identity, i.e., $f: x \mapsto x$, and then you are done, because, obviously, if the boolean formula $\phi$ is satisfiable (and in conjunctive form where each clause has at most three literals), i.e., in 3SAT, then $f(\phi)=\phi$...
4
If you simply uniformly at random (i.i.d) color each of the vertices of $V$ by each of the three possible colors, then for every edge $e\in E$, it's endpoint will be colored by different colors w.p. $\frac{2}{3}$, hence the expected quality of the random coloring is exactly $\frac{2|E|}{3}$. We know that the optimal quality is at most $q^*\leq |E|$, hence ...
4
The paper "A Simplified NP-Complete Satisfibility Problem" given as a reference in the scribe note has actually answered your questions.
Theorem 2.4: Every instance of $r,r$-SAT is satisfiable.
This implies that 3SAT-$3$ is satisfiable.
In addition, Section 3 gives polynomial algorithm for the 2-occurrence case for any $m$-SAT instances ($m \ge 2$).
...
Only top voted, non community-wiki answers of a minimum length are eligible