Hot answers tagged

25 votes

Can anyone give me an instance of 3SAT with exactly one solution?

The empty 3SAT instance (over no variables) has one solution.
SortOfPedantic's user avatar
17 votes

What is wrong with this simple proof of P=NP?

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 ...
Kyle Jones's user avatar
  • 8,071
17 votes

Can anyone give me an instance of 3SAT with exactly one solution?

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 $...
Nathaniel's user avatar
  • 13.9k
16 votes
Accepted

Can anyone give me an instance of 3SAT with exactly one solution?

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) \...
Yuval Filmus's user avatar
14 votes
Accepted

Is a "local" version of 3-SAT NP-hard?

$(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 ...
John L.'s user avatar
  • 38.8k
12 votes
Accepted

Reduction 3SAT and CLIQUE

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. ...
Yuval Filmus's user avatar
11 votes

Can anyone give me an instance of 3SAT with exactly one solution?

One variable: $(A \lor A \lor A)$
Nayuki's user avatar
  • 881
10 votes
Accepted

Random restarts for unsatisfiable instances

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 ...
Kyle Jones's user avatar
  • 8,071
9 votes
Accepted

Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?

$u = (a \vee b) \iff (u \vee \bar{a}) \wedge (u \vee \bar{b}) \wedge (\bar{u} \vee a) \wedge (\bar{u} \vee b) =1 $ Unfortunately, the equivalence above does not hold. Let $a=\text{false}$, $b=\text{...
John L.'s user avatar
  • 38.8k
8 votes
Accepted

How to show ExactOneSAT is NP-Complete?

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} ...
Sarvottamananda's user avatar
8 votes

Results on the difficulty of specific random 3-SAT problems?

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, ...
Yuval Filmus's user avatar
7 votes
Accepted

Randomized algorithm for 3SAT

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 ...
Yuval Filmus's user avatar
6 votes
Accepted

Do polynomial reduction functions work both ways?

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 ...
chi's user avatar
  • 14.5k
6 votes

Expressing 3-SAT in first-order logic

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 ...
Hans Hüttel's user avatar
  • 2,486
6 votes

How to use an algorithm to find a satisfying assignment in polynomial time?

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 ...
adrianN's user avatar
  • 5,931
6 votes

Is integer factorization reducible to subset sum?

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 ...
D.W.'s user avatar
  • 158k
5 votes

NOT satisfiable 3SAT instance certificate

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 ...
Yuval Filmus's user avatar
5 votes

How hard is random SAT?

Theoretically, we don't know how hard k-SAT is; P ?= NP remains an open question. Empirically, random $k$-SAT at the critical clause/variable ratio for each $k$ seems to require exponentially more ...
Kyle Jones's user avatar
  • 8,071
5 votes
Accepted

Why can $2$-SAT be solvable efficiently, but $3$-SAT not?

As was mentioned in a comment we can only say that 3SAT is NP-hard. In 2SAT you can take a variable $x$ and set it to true (or false). Then you can throw out any clauses where $x$ appears, or if a ...
raka's user avatar
  • 166
4 votes

How to choose between UC and PL when using the DPLL algorithm?

If you use the original specification of the DPLL algorithm, in which the unit rule is applied to a fixed point and then the pure literal rule, then only the unit rule is needed to reach a satisfying ...
Kyle Jones's user avatar
  • 8,071
4 votes
Accepted

Why does the reduction from 3SAT to IS work?

The $\Rightarrow$ implication means that you need to prove that if the given $3SAT$ formula is satisfiable then there is a maximum IS. So assume that the formula is satisfiable. Since the formula ...
fade2black's user avatar
  • 9,817
4 votes
Accepted

3-SAT with 3 variable occurences

Your second step isn't sound. Take any unsatisfiable $3$-SAT formula (without restriction on the number of variable appearances) and perform the standard reduction to a formula where each variable ...
David Richerby's user avatar
4 votes
Accepted

Prove "almost clique" is NP complete

You can reduce to this from $CLIQUE$. Given a graph $G=(V,E)$ and $t$, construct a new graph $G^*$ by adding two new vertices $\{v_{n+1},v_{n +2}\}$ and connecting them with all of $G$'s vertices but ...
Don Fanucci's user avatar
4 votes

monotone min-3-sat polynomial algorithm?

3SAT is NP-complete. Positive 3SAT (where all literals are positive) is in P, and thus presumably not NP-complete. There is an even simpler algorithm for Positive 3SAT: set all variables to true. ...
D.W.'s user avatar
  • 158k
4 votes
Accepted

How does the number of clauses affect the difficulty of a 3-SAT problem?

In general, there is no connection. An instance with a "small" number (say a few thousands) of clauses can be very difficult to solve in practice, while an instance with a "large" number (say several ...
Juho's user avatar
  • 22.5k
4 votes
Accepted

General structure of solutions to 3-SAT circuits

The theory you are after is universal algebra. See the excellent expository article of Hubie Chen, A rendezvous of logic, complexity, and algebra, which contains a streamlined proof of Schaefer’s ...
Yuval Filmus's user avatar
4 votes
Accepted

Is every X3SAT instance with no cycles satisfiable?

The graph below is a positive answer without words. Here is the detailed proof. Definitions Let $X$ be an instance of X3SAT. $X$ is linear if any two clause shares at most one variable. $X$ is ...
John L.'s user avatar
  • 38.8k
4 votes
Accepted

Time complexities of state-of-the-art SAT solvers with respect to length of the formula

For 3SAT, the number of variables is polynomially related to the number of clauses. (See the end for the justification.) Consequently, any algorithm for 3SAT whose running time is polynomial in the ...
D.W.'s user avatar
  • 158k
4 votes

Is the following problem NP-Complete?

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 ...
j_random_hacker's user avatar
4 votes

Proof that 2-sat is P-hard?

2SAT is NL-complete (with respect to logspace reductions). Wikipedia outlines a proof: We start by describing Krom's algorithm for 2SAT, using the implication graph. In this directed graph, the ...
Yuval Filmus's user avatar

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