# Questions tagged [sat]

SAT stands for the Boolean satisfiability problem.

307 questions
Filter by
Sorted by
Tagged with
50 views

### How to give a polynomial-time reduction from 3SAT to the Conjunctive Query Evaluation Problem？

How to give a polynomial-time reduction from 3SAT to the Conjunctive Query Evaluation Problem?
65 views

### Why don't we consider that NP = co-NP while we can reduce Tautology problem into Satisfiability in polynomail time easily? [closed]

Let's determine if an expression is tautological or not and let's try this expression: ((a ⊼ b) ∨ c) ↔ (¬a ∨ ¬b ∨ c). We can turn this problem into CIRCUIT-SAT decision problem by asking if the ...
59 views

### Short UNSAT Certificates for X3SAT

Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
68 views

### Direct fpt reduction from Weighted 3SAT to Weighted 2SAT

In parameterized complexity, for each fixed $q$, the problem Weighted $q$-CNF SAT is W-complete. In particular, this means that one can turn a 3CNF formula $\varphi$ into a 2CNF formula $\varphi'$ ...
1 vote
121 views

### proof that 2-SAT is P-hard [closed]

i'm doing university work about the 2-sat problem and it is asked why 2-sat is p-hard. We discussed that 3-sat is np-hard and proved this by reduction from cnf-sat to 3cnf-sat. for my work the ...
170 views

### Complexity of the Complete (3,2) SAT problem?

A complete $k$-CNF formula is a $k$-CNF formula which contains all clauses of size $k$ or lower it implies. Deciding the satisfiability of a complete $k$-CNF formula is clearly a tractable problem ...