# Questions tagged [sat]

SAT stands for the Boolean satisfiability problem.

330 questions
Filter by
Sorted by
Tagged with
22 views

### How often can a clause cause a conflict?

This question is about DPLL+CDCL algorithms. How often can a clause cause a conflict? I want to use a specific algorithm. Assume a DPLL+CDCL SAT solver using a fixed variable order. Variables and unit ...
29 views

97 views

### When the tree-like resolution size is the same with general(regular) resolution size？

Background: For an unsatisfiable SAT formulas, the length of a resolution refutaion means the number of clauses in it. It's well known that there exist exponential separation between tree-like and ...
91 views

### What kind of solver should I use for this hypergraph problem?

I have to list the solutions to the following hypergraph problem: There is a set of nodes, linked by edges that are 2-to-1 and bidirectional. The possible directions are either direct: 2 sources and 1 ...
42 views

101 views

### Resource on the Lee-Yang zeroes of the partition function of random $3$-SAT problems

Could anyone point me to the representative papers on the study of the Lee-Yang zeroes of the partition function of random $3$-SAT problems?
257 views

### Are there analogous works to PPSZ algorithm for #P?

The PPSZ algorithm tells us that we can do SAT-solving for $k-$CNF in time at-most $2^{1-(1-o(1))\frac{\pi^2}{6k}}$. My question is that do we know such results for counting problems in class #P too ? ...
Given a formula in propositional logic with $100$ variables. We know that there can be no SAT-checking provably faster than $O(2^n)$, unless P=NP. Now let's say I could find an algorithm which does ...