Принцип Яо (применение матричных игр для оценки сложности вероятностных алгоритмов), нижняя оценка средней сложности вероятностных алгоритмов сортировки. Две формулировки PCP-теоремы: NP-трудность GAP-3SAT и NP=PCP(log n, 1). Трудность приближения MAX3SAT и задачи о клике.