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

Question

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

Answer 1

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