Ist die Minimierung der Booleschen Ausdrücken NP-Complete?

Question

Ich weiß, dass boolean Erfüllbarkeit NP-vollständig, sondern ist die Minimierung / Vereinfachung eines boolean Ausdrucks, mit dem ich meine einen bestimmten Ausdruck in symbolischer Form zu nehmen und einen gleichwertigen, aber vereinfachten Ausdruck in symbolischer Form, NP-Complete produzieren? Ich bin nicht sicher, dass es eine Reduktion von Erfüllbarkeit zu minimieren, aber ich fühle mich wie es wahrscheinlich ist. Kennt jemand sicher?

Answer 1

Nun, schauen Sie es auf diese Weise: ein Minimierungs Algorithmus verwenden, können Sie alle nicht erfüllbar Ausdruck wörtlichen false kompakt, nicht wahr? Dies löst effektiv TV. So zumindest ein vollständiger Minimierungsalgorithmus gebunden sein NP-vollständig NP hart.