Является ли минимизация логических выражений NP-полной?

Question

Я знаю, что логическая выполнимость является NP-полной, но является ли минимизация/упрощение логического выражения, под которым я подразумеваю взятие данного выражения в символической форме и создание эквивалентного, но упрощенного выражения в символической форме, NP-полным?Я не уверен, что существует сведение от выполнимости к минимизации, но мне кажется, что оно, вероятно, есть.Кто-нибудь знает наверняка?

Answer 1

Ну, посмотрите на это так:используя алгоритм минимизации, вы можете сжать любое невыполнимое выражение до литерала false, верно?Это эффективно решает SAT.Таким образом, по крайней мере, должен быть полный алгоритм минимизации. NP-полный НП тяжело.