Открытая лекция: задача выполнимости булевых формул

[amarao]

застрял на фразе «exists an interpretation». Что такое «interpretation» для булевого выражения? Набор аргументов?

[CaptainTrunky]

Да. Если есть булева формула F (x0, x1, x2), то конкретные значения x0, x1, x2 (истина или ложь) называют интерпретацией. Соответственно, интерпретации могут быть ложжными и истиными (в зависимости от значения F).

[mimicria]

Классическая np-задача. Проверка решения (сертификата, интерпретации) полиномиальна, поиск решения экспоненциален.
Моя любимая задача из семи задач тысячелетия =)