<p>[Edited for clarity]</p>

<p>The most widely used definition in the research literature is the one that requires exactly k distinct variables per clause, and no duplicate clauses.  If you relax the distinct variables restriction, much of the existing research won't make sense to you because your results will not match their results.  The well known sat/unsat phase transition will occur at a different clause-to-variable ratio (if the transition exists at all) and you won't find the hard SAT instances where you'd expect from the literature.</p>

CC BY-SA 3.0
2011-12-21T20:59:57.800Z
This is interesting. Do you happen to have a reference?
Huck Bennett
CC BY-SA 3.0
2011-12-21T22:20:23.067Z
[Generating Hard Satisfiability Problems](http://www.cs.cornell.edu/selman/papers/pdf/96.aij.generating.pdf) by Mitchell, Selman and Levesque.  Section 4 describes what they call "Random K-SAT."  The paper doesn't talk about relaxing the restrictions; that comes from my modifying a random 3SAT generator and feeding many instances into a typical DPLL-based SAT solver.
Kyle Jones
CC BY-SA 3.0
2011-12-22T02:50:54.173Z
“The most correct definition is the one that produces the sat/unsat phase transition at around 4.26 clauses per variable for random 3SAT.”  You must be kidding.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-22T04:14:31.240Z
Change "most correct" to "least confusing" if you prefer.  I wrote it that way because that's how the question was phrased.
Kyle Jones
CC BY-SA 3.0
2011-12-22T06:45:32.437Z
@Tsuyoshi: While "most correct" is definitely a stretch, I think the argument is that this version is standard and one of the best studied.
Huck Bennett
CC BY-SA 3.0
2011-12-23T00:34:06.020Z
I do not believe the answer is correct.
Tayfun Pay
CC BY-SA 3.0
2011-12-24T21:38:21.397Z
@TayfunPay: Please detail your objections.
Kyle Jones
CC BY-SA 3.0
2011-12-24T22:00:18.433Z
You are making a bizarre claim that 4.26 is the magic number which distinguishes a particular definition of term “random k-SAT” as the most correct one.  If this is not a joke, I do not know what to say.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-25T01:45:03.097Z
No, I'm making the claim that the discovery of the phase transition and all the subsequent research and papers that followed agree on the default definition of random k-SAT, which is the definition I gave.  If you use a different definition a lot of papers aren't going to make sense to you because your results won't match their results.  If you're working on a SAT solver, you'll find easy instances where every related paper I've read says you should find hard ones.  There's nothing magical about it, just established convention at this point.  If you want to cite counterexamples, then do that.
Kyle Jones
CC BY-SA 3.0
2011-12-25T02:05:07.210Z
You should read your own answer; if you did, you should read it again.  What you wrote in the last comment is reasonable unlike the answer.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-25T04:25:55.610Z
Fair enough.  I've edited my answer.  Thanks for the critique.
Kyle Jones
CC BY-SA 3.0
2011-12-27T20:21:14.587Z
@KyleJones, I was under the impression that, in the limit sufficiently near the transition, the differences in choosing with or without variable replacement per clause or including or excluding duplicate clauses vanished.  Could you provide some references discussing the difference of the phase transition point or provide intuition as to why the phase transition point wouldn't be the same in the large system limit?
user834
CC BY-SA 3.0
2011-12-28T02:28:15.407Z
@user834 You are correct in the limit.  The probability of 1- and 2-CNF clauses and tautologies being random selected decreases as the number of variables increases for static clause/variable ratios.  So the phase transition values should converge as n increases.
Kyle Jones
CC BY-SA 3.0
2011-12-21T19:26:25.943Z
2011-12-25T04:24:59.280Z
2011-12-25T04:24:59.280Z
Kyle Jones
<p>As was pointed out at the beginning of this discussion in the comments, there is not necessarily a single "right" definition for random $k$-SAT.</p>

<p>That said, the two most common variants of random $k$-SAT are both fixed clause length (FCL) models, meaning that <em>exactly</em> $k$ literals appear in each clause. These variants both disallow repeated variables and literals within a clause, but differ in whether they allow repeated clauses within a formula. Nevertheless, they are essentially the same as will be discussed below.</p>

<p><strong>Two main models:</strong></p>

<p>The <a href="http://www.cs.sfu.ca/~mitchell/papers/aij-hsat.ps">Selman random model</a> - Repeated clause are <em>allowed</em>. Kyle gave this nice reference in the comments to his answer, but incorrectly assumed that the model disallowed repeated clauses. The linked (slightly different) version of the paper contains a more detailed discussion of the random model in Section 3: "This method of generation allows duplicate clauses in a formula... However, as N gets large duplicates will become rare because we generally select only a linear number of clauses."</p>

<p>The Achlioptas random model - Repeated clauses are <em>disallowed</em>. We treat generating a random formula as selecting $m$ clauses u.a.r. from the $2^k {n \choose k}$ total possible clauses without replacement. See Ch.8 of the <a href="http://profs.info.uaic.ro/~croitoru/oc/Handbook%20of%20Satisfiability.pdf">Handbook of Satisfiability</a> [1]  (Random SAT by Achlioptas) as a reference. This model seems more prevalent in the theoretical literature, possibly because so much of it was written by Achlioptas himself.</p>

<p><strong>Equivalence of phase transition locations</strong>:</p>

<p>However, the phase transition (50% satisfiability threshold) occurs at the same clause-to-variable ratio regardless of which of these models is chosen for essentially the reason that Selman et al. noted in their paper.</p>

<p>Let $A(n,m,k)$ denote the expected number of identical pairs of clauses in a Selman random $(n,m,k)$-SAT instance. The probability of a given pair of clauses being identical is $p = 1/(2^k {n \choose k})$, whereas the total number of pairs of clauses is $N = {m \choose 2}$. By the linearity of expectation, $A(n,m,k) = p \cdot N = {m \choose 2}/{2^k {n \choose k}}$.</p>

<p>By Theorem 3 in  [1], the <em>provable</em> upper bound on the location of the $k$-SAT phase transition, using the Achlioptas model occurs when $m = O(2^k n)$. Fixing $k \geq 3$ and setting $m = O(2^k n)$ we get</p>

<p>$A(n,m,k) = {m \choose 2}/{2^k {n \choose k}} = O(m^2)/O(n^k) = O(n^2)/O(n^k)$.</p>

<p>Then, because $k \geq 3$, $\displaystyle \lim_{n \rightarrow \infty} O(n^2)/O(n^k) = 0$, meaning that in expectation there will be zero repeated clauses around the $k$-SAT phase transition when generating random SAT formulas using the Selman model.</p>

<p>Shameless self promotion - I discuss these topics briefly in Section 4.1 of my <a href="https://csel.cs.colorado.edu/~bennethd/thesis/thesis.pdf">master's thesis</a>.</p>

<p><strong>Random QBF</strong></p>

<p>As it turns out, the situation is much more interesting for random QBF. What are AFAIK the first three papers on random QBF each proposed a new random model, critiquing their predecessor.</p>

<p>See the following papers:</p>

<ul>
<li>Cadoli et al. "Experimental Analysis of the Computational Cost of Evaluating Quantified Boolean Formulae." AI*IA 1997</li>
<li>Gent + Walsh "Beyond NP: the QSAT phase transition." AAAI/IAAI 1999</li>
<li>Chen + Interian "A Model for Generating Random Quantified Boolean Formulas." IJCAI 2005</li>
</ul>

CC BY-SA 3.0
2012-05-08T22:52:45.733Z
2012-05-08T22:52:45.733Z
Huck Bennett
<p>There are 4 different constraints we can have when defining Random K-SAT. <br>1)Total number of literals in a given clauses is exactly K or AT most K<br>
2)A given literal can be used with or without replacement in the same clause (A or A or A)<br>
3)A given variable can be used with or without replacement in the same clause (A or ~A or ~A)<br>
4)A given clauses can be used with or without replacement in a given formula<br>
What would be the most "correct" definition? What are the cons and pros of using these different definitions? </p>

CC BY-SA 2.5
2011-01-30T15:29:45.753Z
I do not think that there is a single universally accepted definition.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-30T16:45:27.173Z
I think there are not much difference between those you have stated, it can be helpful if you explain the motivation behind the question.
Kaveh
CC BY-SA 2.5
2011-01-30T17:10:55.720Z
Yet another different choice you can make is whether to choose a fixed number of clauses (with or without replacement) or to choosee a Poisson sample (each clause is included independently with a fixed probability).
David Eppstein
CC BY-SA 2.5
2011-01-30T18:32:14.183Z
Which is the utility of options 2, 3 and 4? Repeating literals in the same clause is unuseful (because such repeated literals are absorbed and don't change the solution space). Repeating variables in the same clause is unuseful because it either falls into option 2 or leads to a trivial (i.e. tautological) clause (which leaves the solution space unaltered). Repeating the same clause is unuseful, too: the clause is absorbed and the solution space remains the same. Only option 1 makes sense.
Giorgio Camerani
CC BY-SA 2.5
2011-01-30T18:48:53.290Z
Walter. Thank you for your comment. However, there are a lot of papers that are out there that repeat literals, variables & clauses. It seems to especially common in papers related to phase transition.
Tayfun Pay
CC BY-SA 2.5
2011-01-30T19:07:14.720Z
@Walter: Repeated literals may be useful if one wants to have exactly k terms per clause (option 1), either as part of the definition of the random distribution or as a notational convenience.
David Eppstein
CC BY-SA 2.5
2011-01-30T19:25:52.760Z
@Geekster: You are welcome. My personal opinion is that taking into account such repeated literals, variables and clauses may lead to erroneous (or at least biased) conclusions. I think they should be avoided: any formula should be "cleaned" first, before being part of any probabilistic/statistical consideration. But this is only an opinion, of course.
Giorgio Camerani
CC BY-SA 2.5
2011-01-30T19:42:58.870Z
Walter, I agree with you 100%. However, people in the field do not seem to think the same way! Furthermore, this problem also arises when you want to go from CNF to DNF or other way around.
Tayfun Pay
CC BY-SA 2.5
2011-01-30T20:11:02.640Z
@David: Thanks. But...don't you think that allowing such repetitions may result in reaching biased conclusions? As far as I know, in order to have exactly $k$ literals per clause (option 1) new dummy variables are introduced (as happens in the proof of 3-SAT NP-Completeness), instead of using options 2 and 3. Is using options 2 and 3 a common practice to achieve exactly $k$ literals? I mean, if someone asks me "How many literals are there in clause $x_1 \lor \lnot x_2 \lor x_1$?", I would certainly answer "2", I would never say "3".
Giorgio Camerani
CC BY-SA 2.5
2011-01-30T20:46:44.837Z
@Walter: isn't it more difficult to sample and argue about those distributions? do they really have a large effect on the distribution? (i.e. what is the probability of having one of these events when n goes to infinity?)
Kaveh
CC BY-SA 2.5
2011-01-30T20:48:53.203Z
@Walter: Although I am not familiar with the literature on random k-SAT, I would guess that both conventions have been used in the literature.  Whether it is “biased” or not depends on what you want to apply the results to.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-30T20:49:55.417Z
@Geekster: “What definition do the state of the art SAT solvers use?”  Do SAT solvers use random k-SAT in any way?  I do not think so (possibly except for benchmarking).
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-30T21:01:49.163Z
@Tsuyoshi Ito: What definition is being used by the SAT Solvers then? Do you know?
Tayfun Pay
CC BY-SA 2.5
2011-01-30T21:02:40.270Z
Why do SAT solvers ever need a definition of random k-SAT?  They only deal with k-SAT, not random k-SAT.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-30T21:35:14.387Z
I don't know that having repeated terms is exactly a "common option", but I've seen it in published papers, for instance Krom (Z. Math. Logik 1967, possibly the first paper on 2-SAT). In that paper there's nothing about randomness, but he uses exactly two terms per clause (which may both be the same) to keep his notation cleaner.
David Eppstein
CC BY-SA 2.5
2011-01-30T22:10:03.787Z
@Kaveh: Yes maybe the bias, if it ever existed, is so negligible that we can ignore it.
Giorgio Camerani
CC BY-SA 2.5
2011-01-30T22:30:25.143Z
@Tsuyoshi, Geekster: I agree with Tsuyoshi, as far as I know SAT Solvers don't need any definition of Random k-SAT, whatever technique they use (DPLL, local search, survey propagation). I'm 100% sure that any serious SAT Solver will remove duplicated clauses, tautological clauses, and duplicated literals before starting the search. Some solvers also remove subsumed clauses.
Giorgio Camerani
CC BY-SA 2.5
2011-01-30T22:35:39.443Z
I do not think that there is an answer to the question in the current form because no definitions seem “more correct” than others and “cons and pros” presumably depend on what you want to use results on random k-SAT for.  I voted to close it as not a real question.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-01T00:00:37.590Z
Tsuyoshi, I disagree with you 100%. If you have read any paper dealing with phase transition, you would have seen that each paper uses a different definition. Some repeat clauses, some repeat variables and so on. I think your decision to close this for an answer is not justifiable.
Tayfun Pay
CC BY-SA 2.5
2011-02-01T00:12:02.627Z
flag
 
@Walter: Although I am not familiar with the literature on random k-SAT, I would guess that both conventions have been used in the literature. Whether it is “biased” or not depends on what you want to apply the results to. – Tsuyoshi Ito yesterday << You even state that you are not familiar with literature on Random K-SAT. Then why are you voting to close this question?
Tayfun Pay
CC BY-SA 2.5
2011-02-01T01:52:17.587Z
I guess the question can be restated, removed the "most correct" part, and concentrate on the cons and pros under some specific results. (Or the answer may go through each possible result.) Since this question is somehow similar to [a question about sparest cut](http://cstheory.stackexchange.com/q/4652/1800) which seems to be within scope with no argument, personally I would like to see the question remains open.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-01T20:52:18.053Z
Your argument (that each paper uses a different definition) precisely justifies my claim that this question is not answerable.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-01T22:18:39.497Z
@Tsuyoshi.  I would like to know the reasons WHY they are using the different definitions. Why not stick to the definition that doesn't repeat literals, variables or clauses at all???. You even stated yourself that you are not familiar with the Random K-SAT literature. Then how can you be the judge on if this question is valid or not?
Tayfun Pay
CC BY-SA 2.5
2011-02-01T22:27:12.053Z
Accept the fact that the current question is not stated in an answerable form.  Either define “correct” or rewrite the question.  This is my last comment in this thread.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-01T22:37:26.970Z
No it is a very acceptable question. Please do not comment or vote on it if you do not even know the literature concerning the question. Thanks
Tayfun Pay
<cc.complexity-theory><sat><randomness><phase-transition>
What is the precise definition of Random K-SAT?
Tayfun Pay
# What is the precise definition of Random K-SAT?

(Asked by: username_0 on 2011-01-30)

There are 4 different constraints we can have when defining Random K-SAT.   
1)Total number of literals in a given clauses is exactly K or AT most K  
2)A given literal can be used with or without replacement in the same clause (A or A or A)  
3)A given variable can be used with or without replacement in the same clause (A or ~A or ~A)  
4)A given clauses can be used with or without replacement in a given formula  
What would be the most "correct" definition? What are the cons and pros of using these different definitions?

**Tags:** cc.complexity-theory, sat, randomness, phase-transition
> **Comments:**
> **username_1**: I do not think that there is a single universally accepted definition.  
> **username_2**: I think there are not much difference between those you have stated, it can be helpful if you explain the motivation behind the question.  
> **username_3**: Yet another different choice you can make is whether to choose a fixed number of clauses (with or without replacement) or to choosee a Poisson sample (each clause is included independently with a fixed probability).  
> **username_4**: Which is the utility of options 2, 3 and 4? Repeating literals in the same clause is unuseful (because such repeated literals are absorbed and don't change the solution space). Repeating variables in the same clause is unuseful because it either falls into option 2 or leads to a trivial (i.e. tautological) clause (which leaves the solution space unaltered). Repeating the same clause is unuseful, too: the clause is absorbed and the solution space remains the same. Only option 1 makes sense.  
> **username_0**: Walter. Thank you for your comment. However, there are a lot of papers that are out there that repeat literals, variables & clauses. It seems to especially common in papers related to phase transition.  
> **username_3**: @Walter: Repeated literals may be useful if one wants to have exactly k terms per clause (option 1), either as part of the definition of the random distribution or as a notational convenience.  
> **username_4**: @Geekster: You are welcome. My personal opinion is that taking into account such repeated literals, variables and clauses may lead to erroneous (or at least biased) conclusions. I think they should be avoided: any formula should be "cleaned" first, before being part of any probabilistic/statistical consideration. But this is only an opinion, of course.  
> **username_0**: Walter, I agree with you 100%. However, people in the field do not seem to think the same way! Furthermore, this problem also arises when you want to go from CNF to DNF or other way around.  
> **username_4**: @David: Thanks. But...don't you think that allowing such repetitions may result in reaching biased conclusions? As far as I know, in order to have exactly $k$ literals per clause (option 1) new dummy variables are introduced (as happens in the proof of 3-SAT NP-Completeness), instead of using options 2 and 3. Is using options 2 and 3 a common practice to achieve exactly $k$ literals? I mean, if someone asks me "How many literals are there in clause $x_1 \lor \lnot x_2 \lor x_1$?", I would certainly answer "2", I would never say "3".  
> **username_2**: @Walter: isn't it more difficult to sample and argue about those distributions? do they really have a large effect on the distribution? (i.e. what is the probability of having one of these events when n goes to infinity?)  
> **username_1**: @Walter: Although I am not familiar with the literature on random k-SAT, I would guess that both conventions have been used in the literature.  Whether it is “biased” or not depends on what you want to apply the results to.  
> **username_1**: @Geekster: “What definition do the state of the art SAT solvers use?”  Do SAT solvers use random k-SAT in any way?  I do not think so (possibly except for benchmarking).  
> **username_0**: @Tsuyoshi Ito: What definition is being used by the SAT Solvers then? Do you know?  
> **username_1**: Why do SAT solvers ever need a definition of random k-SAT?  They only deal with k-SAT, not random k-SAT.  
> **username_3**: I don't know that having repeated terms is exactly a "common option", but I've seen it in published papers, for instance Krom (Z. Math. Logik 1967, possibly the first paper on 2-SAT). In that paper there's nothing about randomness, but he uses exactly two terms per clause (which may both be the same) to keep his notation cleaner.  
> **username_4**: @Kaveh: Yes maybe the bias, if it ever existed, is so negligible that we can ignore it.  
> **username_4**: @Tsuyoshi, Geekster: I agree with Tsuyoshi, as far as I know SAT Solvers don't need any definition of Random k-SAT, whatever technique they use (DPLL, local search, survey propagation). I'm 100% sure that any serious SAT Solver will remove duplicated clauses, tautological clauses, and duplicated literals before starting the search. Some solvers also remove subsumed clauses.  
> **username_1**: I do not think that there is an answer to the question in the current form because no definitions seem “more correct” than others and “cons and pros” presumably depend on what you want to use results on random k-SAT for.  I voted to close it as not a real question.  
> **username_0**: Tsuyoshi, I disagree with you 100%. If you have read any paper dealing with phase transition, you would have seen that each paper uses a different definition. Some repeat clauses, some repeat variables and so on. I think your decision to close this for an answer is not justifiable.  
> **username_0**: flag   @Walter: Although I am not familiar with the literature on random k-SAT, I would guess that both conventions have been used in the literature. Whether it is “biased” or not depends on what you want to apply the results to. – Tsuyoshi Ito yesterday << You even state that you are not familiar with literature on Random K-SAT. Then why are you voting to close this question?  
> **username_5**: I guess the question can be restated, removed the "most correct" part, and concentrate on the cons and pros under some specific results. (Or the answer may go through each possible result.) Since this question is somehow similar to [a question about sparest cut](http://cstheory.stackexchange.com/q/4652/1800) which seems to be within scope with no argument, personally I would like to see the question remains open.  
> **username_1**: Your argument (that each paper uses a different definition) precisely justifies my claim that this question is not answerable.  
> **username_0**: @Tsuyoshi.  I would like to know the reasons WHY they are using the different definitions. Why not stick to the definition that doesn't repeat literals, variables or clauses at all???. You even stated yourself that you are not familiar with the Random K-SAT literature. Then how can you be the judge on if this question is valid or not?  
> **username_1**: Accept the fact that the current question is not stated in an answerable form.  Either define “correct” or rewrite the question.  This is my last comment in this thread.  
> **username_0**: No it is a very acceptable question. Please do not comment or vote on it if you do not even know the literature concerning the question. Thanks  

---

## 2 answers

### Answer by username_7 on 2012-05-08. Score: 17 | Accepted answer

As was pointed out at the beginning of this discussion in the comments, there is not necessarily a single "right" definition for random $k$-SAT.

That said, the two most common variants of random $k$-SAT are both fixed clause length (FCL) models, meaning that *exactly* $k$ literals appear in each clause. These variants both disallow repeated variables and literals within a clause, but differ in whether they allow repeated clauses within a formula. Nevertheless, they are essentially the same as will be discussed below.

**Two main models:**

The [Selman random model](http://www.cs.sfu.ca/~mitchell/papers/aij-hsat.ps) - Repeated clause are *allowed*. Kyle gave this nice reference in the comments to his answer, but incorrectly assumed that the model disallowed repeated clauses. The linked (slightly different) version of the paper contains a more detailed discussion of the random model in Section 3: "This method of generation allows duplicate clauses in a formula... However, as N gets large duplicates will become rare because we generally select only a linear number of clauses."

The Achlioptas random model - Repeated clauses are *disallowed*. We treat generating a random formula as selecting $m$ clauses u.a.r. from the $2^k {n \choose k}$ total possible clauses without replacement. See Ch.8 of the [Handbook of Satisfiability](http://profs.info.uaic.ro/~croitoru/oc/Handbook%20of%20Satisfiability.pdf) [1] (Random SAT by Achlioptas) as a reference. This model seems more prevalent in the theoretical literature, possibly because so much of it was written by Achlioptas himself.

**Equivalence of phase transition locations**:

However, the phase transition (50% satisfiability threshold) occurs at the same clause-to-variable ratio regardless of which of these models is chosen for essentially the reason that Selman et al. noted in their paper.

Let $A(n,m,k)$ denote the expected number of identical pairs of clauses in a Selman random $(n,m,k)$-SAT instance. The probability of a given pair of clauses being identical is $p = 1/(2^k {n \choose k})$, whereas the total number of pairs of clauses is $N = {m \choose 2}$. By the linearity of expectation, $A(n,m,k) = p \cdot N = {m \choose 2}/{2^k {n \choose k}}$.

By Theorem 3 in [1], the *provable* upper bound on the location of the $k$-SAT phase transition, using the Achlioptas model occurs when $m = O(2^k n)$. Fixing $k \geq 3$ and setting $m = O(2^k n)$ we get

$A(n,m,k) = {m \choose 2}/{2^k {n \choose k}} = O(m^2)/O(n^k) = O(n^2)/O(n^k)$.

Then, because $k \geq 3$, $\displaystyle \lim\_{n \rightarrow \infty} O(n^2)/O(n^k) = 0$, meaning that in expectation there will be zero repeated clauses around the $k$-SAT phase transition when generating random SAT formulas using the Selman model.

Shameless self promotion - I discuss these topics briefly in Section 4.1 of my [master's thesis](https://csel.cs.colorado.edu/~bennethd/thesis/thesis.pdf).

**Random QBF**

As it turns out, the situation is much more interesting for random QBF. What are AFAIK the first three papers on random QBF each proposed a new random model, critiquing their predecessor.

See the following papers:

* Cadoli et al. "Experimental Analysis of the Computational Cost of Evaluating Quantified Boolean Formulae." AI\*IA 1997
* Gent + Walsh "Beyond NP: the QSAT phase transition." AAAI/IAAI 1999
* Chen + Interian "A Model for Generating Random Quantified Boolean Formulas." IJCAI 2005


---

### Answer by username_6 on 2011-12-21. Score: 14

[Edited for clarity]

The most widely used definition in the research literature is the one that requires exactly k distinct variables per clause, and no duplicate clauses. If you relax the distinct variables restriction, much of the existing research won't make sense to you because your results will not match their results. The well known sat/unsat phase transition will occur at a different clause-to-variable ratio (if the transition exists at all) and you won't find the hard SAT instances where you'd expect from the literature.

> **Comments:**
> **username_7**: This is interesting. Do you happen to have a reference?  
> **username_6**: [Generating Hard Satisfiability Problems](http://www.cs.cornell.edu/selman/papers/pdf/96.aij.generating.pdf) by Mitchell, Selman and Levesque.  Section 4 describes what they call "Random K-SAT."  The paper doesn't talk about relaxing the restrictions; that comes from my modifying a random 3SAT generator and feeding many instances into a typical DPLL-based SAT solver.  
> **username_1**: “The most correct definition is the one that produces the sat/unsat phase transition at around 4.26 clauses per variable for random 3SAT.”  You must be kidding.  
> **username_6**: Change "most correct" to "least confusing" if you prefer.  I wrote it that way because that's how the question was phrased.  
> **username_7**: @Tsuyoshi: While "most correct" is definitely a stretch, I think the argument is that this version is standard and one of the best studied.  
> **username_0**: I do not believe the answer is correct.  
> **username_6**: @TayfunPay: Please detail your objections.  
> **username_1**: You are making a bizarre claim that 4.26 is the magic number which distinguishes a particular definition of term “random k-SAT” as the most correct one.  If this is not a joke, I do not know what to say.  
> **username_6**: No, I'm making the claim that the discovery of the phase transition and all the subsequent research and papers that followed agree on the default definition of random k-SAT, which is the definition I gave.  If you use a different definition a lot of papers aren't going to make sense to you because your results won't match their results.  If you're working on a SAT solver, you'll find easy instances where every related paper I've read says you should find hard ones.  There's nothing magical about it, just established convention at this point.  If you want to cite counterexamples, then do that.  
> **username_1**: You should read your own answer; if you did, you should read it again.  What you wrote in the last comment is reasonable unlike the answer.  
> **username_6**: Fair enough.  I've edited my answer.  Thanks for the critique.  
> **username_8**: @KyleJones, I was under the impression that, in the limit sufficiently near the transition, the differences in choosing with or without variable replacement per clause or including or excluding duplicate clauses vanished.  Could you provide some references discussing the difference of the phase transition point or provide intuition as to why the phase transition point wouldn't be the same in the large system limit?  
> **username_6**: @user834 You are correct in the limit.  The probability of 1- and 2-CNF clauses and tautologies being random selected decreases as the number of variables increases for static clause/variable ratios.  So the phase transition values should converge as n increases.  

---

