А. Витвицкий

Анализируется эффективность алгоритма случайного блуждания на случайных 3-КНФ формулах. Доказывается линейная верхняя граница на время работы этого алгоритма с плотностью дизъюнктов меньше 1.63. В доказательстве вводиться простое, но мощное средство анализа таких алгоритмов – понятие терминатора, взвешенного выполняющего набора. Показывается что любая КНФ формула имеющая терминатор небольшого веса, решается алгоритмом случайного блуждания за линейное время. Естественно встает вопрос о «терминальном пороге» - максимальной плотности дизъюнктов, для которой с большой вероятностью существует терминатор. Показывается что порог для эвристики свободного литерала (1.63) является нижней границей для терминального порога. Одно из свойств терминаторов то, что они могут быть эффективно найдены с помощью линейного программирования, что представляет эффективно вычислимый сертификат линейного времени работы простого алгоритма случайного блуждания.

Mikhail Alekhnovich, Eli Ben-Sasson. Linear Upper Bounds For Random Walk On Small Density Random 3-CNFs.