"Average-case complexity" - читать интересную книгу автора (Andrej Bogdanov, Luca Trevisan)