We present a new type of sat problem called the k-gd-sat, which generalizes k-sat and gd-
sat. In k-gd-sat, clause lengths have geometric distribution, controlled by a probability
parameter p; for p= 1, a k-gd-sat problem is a k-sat problem. We report on the phase
transition between satisfiability and unsatisfiability for randomly generated instances of k-gd-
sat. We provide theoretical analysis and experimental results suggesting that there is an
intriguing relationship (linear in the parameter 1/p) between crossover points for different …

We present a new type of sat problem called the k-GD-SAT, which generalizes k-sat and GD-
sat. In k-GD-SAT, clause lengths have geometric distribution, controlled by a probability
parameter p; for p= 1, a k-GD-SAT problem is a k-SAT problem. We report on the phase
transition between satisfiability and unsatisfiability for randomly generated instances of k-GD-
SAT. We provide theoretical analysis and experimental results suggesting that there is an
intriguing relationship (linear in the parameter 1/p) between crossover points for different …