We consider Boolean formulas with three literals per clause, or 3-SAT formulas. For random formulas with m clauses over n variables, such as r = m=n is a constant, it has been experimentally observed that, asymptotically as r crosses the threshold value 4:2 (approximately) the probability that Á is satis¯able falls abruptly from nearly 1 to 0. Moreover, as n increases towards larger and larger values, the transition of the probability becomes sharper. The purpose of this paper is to simply outline a connection between the problem of determining bounds to the threshold value and the concept of Kolmogorov complexity.