Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

20
votes
3answers
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 ...
5
votes
1answer
110 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 ...
6
votes
0answers
152 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 ...
11
votes
2answers
429 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 ...
25
votes
2answers
320 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 ...
18
votes
1answer
378 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 ...
6
votes
1answer
254 views

Approximating Random MAX-k-SAT

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 ...
16
votes
1answer
394 views

Average-case tautologies/contradictions, beyond the random k-CNF model

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 $. ...