Аннотация:
Пусть дана формула в конъюнктивной нормальной форме (конъюнкция, каждый член которой представляет собой дизъюнкцию переменных и их отрицаний), в которой каждая дизъюнкция содержит ровно $n$ переменных и каждая переменная входит в не более чем $2^n/8$ дизъюнкций. Такая формула всегда выполнима, хотя это и не очевидно (доказательство использует так называемую лемму Ловаса о пересечении частично независимых семейств событий).
Справедлив и бесконечный аналог этого утверждения: для эффективно заданной (в некотором естественном смысле) бесконечной КНФ с теми же ограничениями всегда есть набор значений, который вычисляется некоторым алгоритмом и делает её истинной. Это доказал Андрей Румянцев, используя недавно найденный вероятностный алгоритм Мозера – Тардоша для поиска выполняющего набора в лемме Ловаса и понятие послойно вычислимого отображения (его предложили Хойруп и Рохас). Он показал, что применение бесконечного аналога алгоритма Мозера – Тардоша даёт послойно вычислимое отображение, которое в свою очередь задаёт вычислимое распределение вероятностей на бесконечных последовательностях нулей и единиц, что позволяет найти искомый выполняющий набор.
|
