Hot answers tagged

22 votes

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

The empty 3SAT instance (over no variables) has one solution.
user avatar
16 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 ...
user avatar
  • 7,853
16 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 $...
user avatar
  • 7,193
15 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) \...
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 ...
user avatar
  • 34.7k
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. ...
user avatar
10 votes

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

One variable: $(A \lor A \lor A)$
user avatar
  • 842
9 votes
Accepted

3-SAT for variables appearing 3 times

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,...
user avatar
9 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 ...
user avatar
  • 7,853
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} ...
user avatar
  • 4,747
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, ...
user avatar
7 votes

The relation between 2SAT and 3SAT

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 ...
user avatar
7 votes
Accepted

The relation between 2SAT and 3SAT

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 ...
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 ...
user avatar
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 ...
user avatar
  • 2,446
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 ...
user avatar
  • 5,910
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 ...
user avatar
  • 14.2k
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 ...
user avatar
  • 143k
5 votes
Accepted

How must Grovers algorithm be modified in order to solve 3-SAT?

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 ...
user avatar
  • 143k
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 ...
user avatar
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 ...
user avatar
  • 166
4 votes
Accepted

3/2 - Approximation probabilistic algorithm for MAX-3-COLOR

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. $\...
user avatar
  • 2,594
4 votes
Accepted

Hardness of 3SAT-k

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. ...
user avatar
  • 9,219
4 votes

How must Grovers algorithm be modified in order to solve 3-SAT?

Notwithstanding D.W.'s answer, the other option, if all you knew about Grover's algorithm is that it requires unique solutions, is to use the work of Valiant and Vazirani. Without getting into details,...
user avatar
4 votes
Accepted

If P != NP, then 3-SAT is not in P

The opposite is valid. $3SAT$ is an $NP$-complete problem, so every problem in $NP$ can be reduced to $3SAT$. If $P \neq NP$ and $3SAT \in P$, every problem in $NP$ would be in $P$, contradicting $P ...
user avatar
  • 1,348
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 ...
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. ...
user avatar
  • 143k
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 ...
user avatar
  • 9,632
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 ...
user avatar
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 ...
user avatar
  • 22.1k

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