On average case complexity

The airn of this talk is to give an introduction to the notion of Levin's average case complexity and then show sorne of the fields were recent research in this area is focused on. The first part is motivated by the struggle to find a precise and generally accepted definition of what is an efficient time on the average algorithm, given some distribution on the input. The definition should be easy (to use) and of course be machine independent and should posses properties like being closed under composition of algorithms. A reduction of a problem A to another problem which is efficiently solvable on average should give an efficient on average procedure to solve A. We then look in more detail at DistNP the class of problems in NP with polynomial time distributions on the inputs. This class has complete and self-reducible problems