Локальная лемма Ловаса, следствие о выполнимости формулы в КНФ. Вероятностный алгоритм поиска выполняющего набора для формулы в m-КНФ, у которой каждый дизъюнкт пересекается по переменным не более, чем с $ 2^m/8 $ другими. Условная колмогоровская сложность. Теорема Колмогорова-Левина. Неравенство $ 2KS(x,y,z)\le KS(x,y)+KS(y,z)+KS(x,z)+O(\log n) $, неравенство о связи объема и площадей проекций трехмерного тела.