Â鶹´«Ã½AV

Random constraint satisfaction problems have been widely studied in the past. In many systems, when the number M of random constraints and the number N of variables go simultaneously to infinity at a fixed ratio alpha=M/N, at low alphas we are in the SAT region, where there is a choice of the variables that satisfies all the constraints, while at high alpha we are in the UNSAT region, where there is no choice of the variables that satisfies all the constraints. The transition from the SAT to the UNSAT region is sharp.

Analytic computations have been done for the value of the transition point in many cases, e.g., the K-SAT problem. However, in the past, the behavior at the transition has been mostly studied in the case where the variables are Boolean. In this talk, I will describe new features that are present near and at the transition in the case where the variables are continuous. In the continuous case, the N Boolean variables are replaced by real variables belonging to an N-dimensional manifold and the usual M boolean constraints are replaced by M inequalities.

A familiar example of a continuous satisfaction problem is to find a feed-forward neural network such that M input patterns are correctly classified; here the N synaptic strengths play the role of the variables and each input pattern provides a constraint.