Report on Generic Case Complexity
Robert H. Gilman, Alexei Myasnikov, Alex D. Myasnikov, Alexander Ushakov · arXiv (Cornell University) · 2007
This article is a short introduction to generic case complexity, which is a recently developed way of measuring the difficulty of a computational problem while ignoring atypical behavior on a small set of inputs. Generic case complexity applies to both recursively solvable and recursively unsolvable problems.