Новые классы КНФ, с полиномиально распознаваемым свойством выполнимости

На основе методов алгебры кортежей [1] разработан алгоритм решения задачи ВЫПОЛНИМОСТЬ КНФ. Доказано, что для класса “плотных” КНФ, у которых “пустые” переменные, не включенные в дизъюнкты, распределены равномерно с вероятностью не более 1/3, сложность этого алгоритма в среднем полиномиальна. Рассмотрены варианты выигрышной стратегии этого алгоритма, позволяющие расширить класс КНФ с полиномиально распознаваемым свойством выполнимости.