# Questions tagged [sat]

SAT stands for the Boolean satisfiability problem.

307 questions
Filter by
Sorted by
Tagged with
8 views

### Do asymptotic bounds for k-SAT algorithms assume the formulas can have up to $O(|V|^k)$ clauses?

Defining the terms: $f_k(V)$ - an unquantified boolean formula in CNF that contains clauses of length up to $k$ literals. $V$ - the set of arguments of $f_k(V)$. $C$ - the set of clauses $f_k(V)$ ...
• 207
42 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 ...
28 views

### Solving K-Flip SAT problem in Polynomial time

Given a dataset with N variables, M clauses in CNF form, and a randomly generated truth assignment T. I am trying to find a truth assignment T' that flips at most k variables and satisfies more ...
30 views
+50

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

In parameterized complexity, for each fixed $q$, the problem Weighted $q$-CNF SAT is W[1]-complete. In particular, this means that one can turn a 3CNF formula $\varphi$ into a 2CNF formula $\varphi'$ ...
• 419
1 vote
102 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 ...
124 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 $k$-CNF formula is clearly a tractable problem since a $k$-...
• 1,069
67 views

• 141
1 vote