AVERAGE CASE COMPUTATIONAL COMPLEXITY

Yuri Gurevich 
University of Michigan

One way to cope with the phenomenon of NP completeness is to try to
solve the problem quickly on average with respect to the relevant
distribution on instances.  That works in many cases, but some
randomized NP problems are hard even in the average case.  We explain,
motivate and justify basic definitions of the average-case reduction
theory, and describe the current state of affairs.  In addition (time
permitting), we discuss the P=?NP question and argue in favor of an
alternative question based on the average-case complexity.