# Questions tagged [3-sat]

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

122 questions
Filter by
Sorted by
Tagged with
42 views

### Difference 2SAT and 3SAT

Hi and good day everyone. This is my first time here. I am new with satisfiability problem. I need to choose between 2Sat or 3Sat for my project. Here is my questions: What is the major difference ...
18 views

### Reducing from SAT to something else

Showing that the following problem is NP-hard. Input: A boolean function in CNF (conjunctive normal form). Output: Three distinct satisfying assignments that evaluate the given function as TRUE, if ...
21 views

### Reducing 3-SAT to restricted 3-SAT

I am trying to show that the following problem is NP-hard. Input: A boolean function in CNF (conjunctive normal form) such that every clause has at most three literals and every variable appears in at ...
70 views

### Is there any algorithm for 3SAT problem that is fast and relatively easy to implement?

Here is the description for 3SAT satisfiability problem. I already know about the DPLL algorithm, but it's implementation is pretty complex. I would like some algorithm that is relatively simpler but ...
35 views

### 1-OR-3-SAT is in P

1-OR-3-SAT: Input: 3-CNF formula $\varphi$ Question: whether there is an assignment $x$ such that in each clause there are one or three true literals. I need to show that this problem is in $P$. I ...
25 views

### Showing resolution algorithm for 2SAT is polynomial time

I don't quite understand why the resolution algorithm completes in polynomial time for 2SAT but not 3SAT. I'm looking at slide 42 of these slides for reference. It is clear that given two clauses of ...
18 views

### 3-OCC-MAX SAT np-complete?

Assuming 3-OCC-MAX SAT is the language of all CNF formulas in which every variable appears in at most 3 clauses. Is this problem NP-Complete? I'm trying to find a karp reduction between SAT and this ...
34 views

### algorithm for checking satisfiability

In order to prove that SAT is in NP, I need to come up with a polynomial time verfier (an algorithm). The Cooks Levin Theorem uses a non-deterministic Turing machine but that's not what I am looking ...
40 views

### Is MAX-averageSAT a well-known problem?

Is there any variant of the Boolean SAT or Max-SAT problem that has a flavor of maximizing or minimizing the average of the weights of the satisfied clauses of a WCNF formula? Any literature on an ...
22 views

### planar 1-in-3 sat described as a planar graph for independent set

Given a planar 1-in-3 sat formula, can someone reduce that formula into a graph that asks the question when ever there is an independent set for it, that's also planar?
93 views

### Is Monotone 3-SAT with exactly 3 distinct variables untractable?

I have given the following SAT variation: Given a formula F in CNF where each clause C has exactly 3 distinct literals and for each C in F either all literals are positive or all literals are negated....
179 views

### Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset

I am working on a problem defined as the following Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our ...
22 views

### Assuming the Exponential Time Hypothesis is true, what's the fastest possible algorithm that can be produced for NP-complete problems? [duplicate]

Assuming the Exponential time hypothesis is true, what's the fast possible algorithm that can be produced for NP-complete problems? If 3-Sat takes exponential time, then could it be possible that ...
20 views

### What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat?

What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat? Would this result in their being a quasi polynomial-time algorithm for all NP-complete problems?
47 views

### When does Gaussian elimination solve exact 1-in-3 SAT?

Terms: A literal is a variable or its negation. A clause is a set of literals. An exact 3-in-1 clause is satisfied if an assignment of values to variables results in exactly 1 ...
57 views