16
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tayfun Pay
    Mar 2 '11 at 19:00
  • 1
    $\begingroup$ @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). $\endgroup$
    – Iddo Tzameret
    Mar 3 '11 at 6:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Mar 3 '11 at 23:18
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Mar 4 '11 at 2:49
  • 3
    $\begingroup$ 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. $\endgroup$
    – Iddo Tzameret
    Mar 4 '11 at 3:52
4
$\begingroup$

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:

Paul Beame, Russell Impagliazzo, and Ashish Sabharwal. The resolution complexity of independent sets and vertex covers in random graphs. Computational Complexity, 16(3):245-297, 2007.

Paul Beame, Joe Culberson, David Mitchell, and Cristopher Moore. The resolution complexity of random graph k-colorability. Discrete Applied Mathematics, 153:25-47, 2005.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.