# 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$. Thus, random $k$-CNF formulas (for $c$ large enough) constitute a natural distribution over unsatisfiable Boolean formulas (or dually, over tautologies, i.e. negations of contradictions). This distribution has been studied extensively.

My question is the following: are there any other established distributions over propositional tautologies or contradictions, that can be considered as capturing the "average-case" of tautologies or unsatisfiable formulas? Have these distributions been intensively studied?

• @Iddo Tautologies do not exists in a "true" CNF model because otherwise you would need to have a literal and its complement in the same clause.... Tautologies are not interesting to study in CNF. – Tayfun Pay Mar 2 '11 at 19:00
• @Pay, the negation of an unsatisfiable formula is obviously a tautology. Hence, we can consider random k-CNF's as a distribution over tautologies (when the clause-to-variable ratio is large enough, and where there is an o(1) probability for a k-CNF to be satisfiable). – Iddo Tzameret Mar 3 '11 at 6:41
• I think that Tayfun is right. You should speak of either CNF formulas being unsatisfiable or DNF formulas being tautologies. In the current question, you are mixing the two. – Tsuyoshi Ito Mar 3 '11 at 23:18
• This is my last comment on this matter: I do not know why you insist to keep the word “tautologies,” which is clearly wrong as Tayfun explained. But I am fine if you do not want to incorporate other people’s comments to improve the wording of your question. – Tsuyoshi Ito Mar 4 '11 at 2:49
• I prefer to keep the term 'tautologies' in the title because I'm asking about distributions on either tautologies or contradictions, and the question is phrased accordingly. – Iddo Tzameret Mar 4 '11 at 3:52

Paul Beame has two papers (with various coauthors) where the resolution complexity of certain distributions of random formulas are studied. These formulas arise by expressing properties, such as k-colorability or having independent sets of size k, of random graphs from the usual distribution $G(n,p)$. Here are the links: