Зачем нам всем нужен SAT и все эти P-NP (часть вторая)
В предыдущей части были освещены общедоступные вопросы, касающиеся SAT и P-NP: история проблемы, интуитивные определения классов и задач, указаны основные приложения SAT и основные последствия, в случаи решения P?= NP (там же можно найти достаточное число ссылок на различный материал для самостоятельного изучения тематики).
В данной статье мы рассмотрим техническую сторону вопроса, а так же формализуем и представим в деталях материал из предыдущей статьи.
картинка из статьи Boolean Satisfiability: From Theoretical Hardness to Practical Success (Communications of ACM) Читать дальше →
