Stochastic models for NP-complete problems attempt to describe the average case of these problems rather than their worst case. The study of these models is a considerable challenge to the probabilists. The project concentrates on problems where connections with other areas of mathematics can be found. The emphasis is on considering the problems at the greatest possible level of generality (which often makes them look much simpler) and on the use of abstract tools rather than adhoc methods. In the past, progress has been made using empirical processes, martingale inequalities, and the Hahn-Banach theorem. Specific problems to be studied include bin packing heuristics, scheduling problems and the traveling salesman problem.
