# Questions tagged [3-sat]

3SAT is a famous special case of the boolean satisfiability problem (SAT).

173 questions
Filter by
Sorted by
Tagged with
36 views

### Is checking whether a a set of 3-literal clause is satisfiable such that every literal in each clause is either all true or all false NP-complete?

I want to know if checking whether a a set of 3-literal clause is satisfiable such that every literal in each clause is either all true or all false NP-complete? By 3-literal clause, I mean it can ...
• 29
32 views

### Generate a minimum number of clauses in 3-CNF form that give a unique solution

Suppose I would like to generate n clauses, in 3-CNF form, that would give a unique solution for m variables (m<n). Example: for m=6, I've got {a,b,c,d,e,f} = 111010 How to generate these n 3-CNF ...
46 views

### Ιf 3SAT reduces to its complement then NP=coNP

Can you please explain to me why the following is true? Ιf 3SAT reduces to its complement then NP=coNP. Thoughts: 3SAT is NP-complete so for every X in NP $X \leq 3SAT$ $\overline {3SAT}$ is NP-...
• 37
1 vote
45 views

### Variation of 3-SAT

I already know that SAT and 3-SAT are NP-complete. If in 3-SAT the Boolean expression should be divided to clauses,such that every clause contains at most (in the original problem it says exactly) ...
• 37
1 vote
54 views

### How to reduce 3SAT to TwoOrMoreSAT?

I want to prove, that 2OrMoreSAT is NP-complete. It's defined as follows: A formula is considered strongly satisfiable if there exists a model such that two or more different literals in every clause ...
30 views

### How to prove that it is NP-complete?

I was trying to do this exercise, but I don't know how to solve this problem is NP-complete, what reduction to do. There is a network N of n people, in which every person i is associated with a subset ...
44 views

### MAX-SAT approximation factor

I am stuck on an exercise that ask the approximation factor of a MAX-SAT approximated algorithm generalized from a MAX-3SAT algorithm MAX-3SAT: set every variable with a random value ($0$ or $1$ each ...
32 views

### 3 SAT polynomial time reduction to SubSet Sum

I am trying to understand the reduction of 3 SAT to Subset Sum, however in all the proofs, they have a 3 CNF formula $\phi$. However no one mentions, how the formula was arrived. For example in CLRS, ...
43 views

### NP-hard $k$-SAT variant with exactly $\ell$ occurrences per variable

For the purpose of this post, let $k$-SAT be SAT with exactly $k$ literals per clause, as opposed to the more common meaning of at most $k$ literals per clause. With the purpose of proving some ...
• 621
28 views

### NP-hard (3-)SAT variant with $n$ clauses and $f(n)$ variables

With the purpose of proving my problem NP-hard, I'd like to reduce from a SAT variant (which of course should remain NP-hard) in which not two parameters are present (typically $n$ clauses and $m$ ...
• 621
1k views

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

Let $a_i$, $b_i$, etc., be a literal, i.e., a variable or the negation of a variable. 3-SAT concerns formulas in CNF form: $(a_1 \vee a_2 \vee a_3) \wedge \dots \wedge (b_1 \vee b_2 \vee b_3)$ (3-CNF)....
25 views

### I'm trying solve a problem using different versions of SAT, how exactly does mixing SAT affect the hardness of the problem?

I'm trying to solve a problem which I can solve in 3SAT or as a mixed 2,3,4 SAT. I know how hard each of those categories are individually and know the derivations of their hardness individually. But ...
• 141