# Questions tagged [3-sat]

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

191 questions
Filter by
Sorted by
Tagged with
1 vote
38 views

### Is Monotone Not-Exactly-1 3SAT solvable in polynomial time?

I'm studying different variants of the SAT problem, and I came across the Monotone Not-Exactly-1 3SAT problem. Specifically, this problem involves determining whether a Boolean formula in CNF, where ...
1k views

### Why can't we prove SAT is NP complete just using the Tseytin Transformation?

The Cook Levin theorem proves SAT is NP-Complete, but it is fairly complicated, non-constructive and uses a Turing machine. I am confused as to why just the Tseytin Transformation does not imply/prove ...
• 43
1 vote
47 views

### is 3-SAT ∈ NTIME(n^3)?

I'm struggling to understand the time complexity of 3-SAT using a non-deterministic Turing machine, as well as the relationship between NTIME and DTIME For example, let's say we have 2 literals. My ...
28 views

### Limited constant degree HamCycle

Let $G=(V,E)$ be a directed graph. I am interested in a "relaxed" version of the HamCycle problem. In my first case, the degree of each vertex is exactly 6, such that: 3 are outgoing edges ...
• 485
1k views

### Why is 3-SAT used for proving NP-Completeness so often?

I was wondering why 3-SAT is often chosen as the candidate problem from which one reduces from to prove the NP-completeness of another algorithm. I've seen it justified in places such as K&T by ...
216 views

### Tseitin formula on 2-connected graph

How can we prove that for $\\\\$ every $\\\\$ 2-connected graph G with an odd number of vertices, the unsatisfiable Tseitin formula for it is minimally unsatisfiable, that is, if we remove even a ...
1 vote
133 views

### Resolution on weakening rule by derived clause

How to prove that every clause that is implied by the input formula (learned or not) can be derived using resolution with weakening rule: $\frac{C} {C \vee D}$ (A clause $C$ is implied by $F$ if for ...
• 542
1 vote
330 views

• 135
107 views

### Complexity of this variant of 3-SAT?

This post introduces a new variant of 3-SAT called EQUAL-3-SAT, where the number of 3-Literal clause is equal to the number of variable. Consider the 3-SAT problem where the formula is in conjunctive ...
• 43
373 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 ...
• 43
178 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 ...
173 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-...
• 57
1 vote
474 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) ...
• 57
1 vote
145 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 ...
32 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 ...
165 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 ...
184 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 ...
• 807
47 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$ ...
• 807
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)....
• 548
28 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 ...
• 151