additional aspect is the investigation of conjunctions of randomly picked constraints; [@MO] is a fundamental study here. Propositional formulas in $k$-conjunctive normalform provide an example which has lead to a rich literature e. g. [@DIAZ]. One of the characteristic properties of this research is that its findings can often be related to experimental work by running algorithms on randomly generated instances.

One of the aspects of random formulas is a threshold phenomenon: If the number of constraints of a conjunction picked is less than a threshold value the conjunction is typically satisfiable, if it is more we get unsatisfiability whp. Moreover instances picked close to the threshold seem to be algorithmically hard, thus being candidate test cases for algorithms. The threshold phenomenon and the possibility to investigate it by experiments causes physics to become interested in the area e. g. [@MEZE]. On the other hand, physical approaches lead to new algorithms and classical theoretical computer science research, e. g. [@COPRI].

One of the major topics is to determine the value of the threshold in natural cases. A full solution even in the natural $k-$CNF SAT case has not been obtained, but many partial results, [@DIAZ] for $k=3.$ Note that $k-$CNF 