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, ...
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$...
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,...
9
First we reduce the task of factorization to finding any factor of $n$ (or showing that it's prime). Once we know how to do this, we divide $n$ by such an factor and repeat the process until all factors are broken down to primes, and this takes $O(\log n)$ steps.
Let $k=\lceil\log_2 n\rceil$ the number of bits in $n$.
Next, we design a binary ...
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 ...
8
Yes you can. Actually you can even show that something stronger is true. The problem know as Positive Planar 1-in-3-SAT is NP-complete as shown by Mulzer and Rote.
In this version of 1-in-3-SAT, you require for every input formula that
you have three variables per clause, none of them negated
the graph of the formula is planar, even if you add the "...
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.
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
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
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
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
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 ...
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 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
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
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
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 ...
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
Hint: Take a valuation $v$ satisfying less than half of the clauses. What about $\bar{v}$ the valuation such that $\bar{v}(x)=\neg v(x)$?
4
Like Kaveh said, you can view a decision problem as a language consisting of the descriptions of all the "yes" instances. Then the Kolmogorov complexity of the language is, as you said, the length of the smallest program that produces all those descriptions.
How we describe the program that generates the instances (and hence defines the Kolmogorov ...
4
We can view of a language $A$ as an infinite binary string (the infinite binary string corresponding to the characteristic function of $A$) and then use the notion of Kolmogorov complexity for such strings.
Google for: Kolmogorov complexity infinite words
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
