# Questions tagged [random-k-sat]

Related to kSAT with a probability distribution over inputs.

10 questions
20 views

### How to calculate the number of variables and total number of clauses in a SAT problem for a specific domain size? [closed]

I have a set of propositional clauses generated by clausification of a set of first-order logic axioms containing 2 binary predicates (p and c). Assume P is the number of distinct predicates in the ...
185 views

### How to benchmark #2-SAT counting algorithms?

Are there any libraries of #2-SAT instances that are hard to solve with state-of-the-art exact solvers (sharpSAT, cachet, ...)? Alternatively: are there practical ways to generate hard #2-SAT ...
1k views

### Has there been any research on $k$-SAT above the satisfiability threshold?

A well known characteristic of $k$-SAT instances is the ratio of the number of clauses $m$ over the number of variables $n$, i.e., the quotient $\rho = m/n$. For every $k$, there is a threshold value ...
138 views

### Empirical probability of k-SAT satisfiability

Given a random instance $I_m = I_m(n,k)$ of $k$-SAT with $n$ variables and $m$ clauses, what's the probability $I_m$ is satisfiable? It's believed that there's a threshold above which satisfiability ...
2k views

### Random 3-SAT: What is the consensus experimental range of the threshold?

The critical ratio of clauses to variables for random 3-SAT is more than 3 and less than 6, and seems to be commonly described as "around 4.2" or "around 4.25". Mezard, Parisi, and Zecchina prove (in ...
674 views

### What's the correlation between treewidth and instance hardness for random 3-SAT?

This recent paper from FOCS2013, Strong Backdoors to Bounded Treewidth SAT by Gaspers and Szeider talks about the link between the treewidth of the SAT clause graph and instance hardness. For ...
407 views

### Current tightest bounds for critical 3-SAT density

I'm interested in the critical 3-satisfiability (3-SAT) density $\alpha$. It's conjectured that such $\alpha$ exists: if the number of randomly generated 3-SAT clauses is $(\alpha + \epsilon) n$ or ...
446 views

### What is the counting complexity of random 2-SAT?

Has any work been done on how the complexity of random instances of #2-SAT varies with the clause density? That is: how does the difficulty of counting satisfying solutions to a randomly generated ...
It is known [de la Vega & Karpinski 2002] that random instances of MAX-3-SAT on $n$ variables can be approximated up to fraction at least 8/9 w.h.p. tending to 1 as $n$ tends to infinity. Should ...
It is well known that random $k$-CNF formulas over $n$ variables with $cn$ clauses are unsatisfiable (i.e. they are contradictions) with high probability, for sufficiently large constant $c$. ...