The is a continuation of the principal investigator's previous research on the average case and probabilistic settings of information-based complexity. Three new research directions will be followed in this investigation. The first is an investigation when intractability or noncomputability in the deterministic worst case setting can be avoided by using randomness or by using average case and probabilistic settings. The second is space complexity for problems with massive amounts of data. The final new direction is the study of optimal algorithms and complexity for nonlinear problems in the average case setting.
