Ist die „Gültiges mathematischer Ausdruck“ Problem P oder NP?

Question

Diese Frage ist rein aus Neugier. Ich bin für den Sommer aus der Schule und wollte einen Algorithmus implementieren, das nur zum Spaß zu lösen. Das führte zu der obigen Frage, wie schwer ist dieses Problem?

Das Problem: Sie erhalten eine Liste von positiven ganzen Zahlen angegeben sind, eine Reihe von mathematischen Operatoren und das Gleichheitszeichen (=). können Sie einen gültigen mathematischen Ausdruck die ganzen Zahlen mit (in der gleichen Reihenfolge) und die Operatoren (beliebig oft) erstellen?

Ein Beispiel wird sollten alle Fragen klären:

gegeben: {2, 3, 5, 25}, {+, -, *, /}, {=}
   Ausgang: JA

der Ausdruck (nur eine glaube ich) (2 + 3) * 5 = 25. Sie nur ausgeben müssen JA / NEIN.

Ich glaube, das Problem in NP ist. Ich sage das, weil es ein Entscheidungsproblem (JA / NEIN-Antwort) ist und ich kann einen nicht-determinis Poly Algorithmus finden, die es entscheidet.

a. nicht-deterministisch eine Folge von Operatoren zwischen den ganzen Zahlen platzieren wählen.
   b. überprüfen Sie beantworten ein gültiger mathematischer Ausdruck ist (dies kann in konstanten erfolgen       Zeit).

In diesem Fall ist die große Frage ist: Ist das Problem in P? (D Gibt es einen deterministischen Poly Zeit Algorithmus, der es entscheidet?) Oder ist das Problem NP vollständig? (Das heißt kann ein bekanntes NP vollständiges Problem auf diese reduziert werden? Oder äquivalent Ist jede NP Sprache Poly Zeit reduzierbar für dieses Problem?) Oder keines von beiden? (D Problem in NP, aber nicht NP Complete)

Hinweis: Diese Problemstellung übernimmt P ungleich NP. Auch, obwohl ich bin hier Überlauf Stack, ich bin vertraut mit dem Hausaufgaben-Tag. Dies ist in der Tat nur Neugier, keine Hausaufgaben:)

Answer 1

Eine einfache Reduzierung der Partition Problem (die NP-Complete ist) - gegeben ein Satz von N ganzen Zahlen S, die Eingabe in das „Gültiges Math“ Problem wäre - die Elemente von S, N-2 ‚+‘ Operatoren und ein Zeichen ‚=‘.

Answer 2

Es scheint eine Art von Verwirrung darüber zu sein, wie für NP-Vollständigkeit zu überprüfen. Ein NP-vollständiges Problem ist mindestens so hart, in einem bestimmten Sinne, wie jedes anderes Problem in NP. Angenommen, wir waren im Vergleich zu 3SAT, da einige Plakate zu tun versuchen.

Nun beweist das gegebene Problem auf 3SAT reduziert nichts. Es ist dann wahr, dass, wenn 3SAT effizient lösen kann (was bedeutet, P = NP) kann das gegebene Problem effizient gelöst werden. Wenn jedoch das gegebene Problem effizient gelöst werden kann, dann vielleicht es entspricht nur leicht Spezialfälle von 3SAT.

Wir hätten 3SAT auf das gegebene Problem zu reduzieren. Das bedeutet, dass wir eine Regel bilden müssten willkürliche 3SAT Probleme Beispiele für das gegebene Problem zu transformieren, so dass die Lösung des gegebenen Problems würde uns sagen, wie das 3SAT Problem zu lösen. Das bedeutet, dass 3SAT nicht härter sein könnte, als das gegebene Problem. Da 3SAT das härteste möglich ist, dann muss das gegebene Problem auch das härteste möglich sein.

Die Reduktion der Partition Problem arbeitet. Das Problem funktioniert wie folgt: a multiset S von ganzen Zahlen angegeben, können wir diese in zwei getrennte Sub-Sätze aufteilen, dass zwischen ihnen umfassen jedes Mitglied von S, so dass die Summen der disjunkte Teilmengen sind gleich

Um dies zu tun, konstruieren wir eine Folge beginnend mit 0, jedes Element von S, und dann 0. Wir verwenden {+, -} als Betrieb gesetzt. Das bedeutet, dass jedes Element von S wird entweder addiert oder subtrahiert, um 0 bis insgesamt, was bedeutet, dass die Summe der hinzugefügten Elemente ist das gleiche wie die Summe der subtrahierten Elemente.

Daher ist dieses Problem zumindest so hart wie das Verteilungsproblem, da wir ein Beispiel Partition Programm lösen können, wenn wir die gegebenen lösen können, und ist daher NP-vollständig.

Answer 3

OK, zuerst, Sie „set“ von ganzen Zahlen, aber eine Menge ist per definitionem ungeordnet, so dass Sie eine „Liste“ von ganzen Zahlen bedeuten.

Auch ich werde eine Annahme hier machen, die falsch sein können, das ist, dass die = Vorzeichen immer genau einmal vorkommt, zwischen dem zweiten und der letzten ganzen Zahl auf Ihrer Liste zu halten. Wenn Sie das Gleichheitszeichen in der Mitte ermöglichen, wird es komplizierter.

Hier ist ein tatsächlicher Beweis dafür, dass „Gültiges mathematischer Ausdruck“ (VME) ist NP vollständig. Wir können eine Reduktion tun von Subset Summe . HINWEIS dass Wikipedia-Definition von Teilmenge Summe setzt voraus, dass die Teilmenge nicht leer ist. In der Tat ist es wahr, dass das allgemeinere Problem der Teilmenge Summe so dass leere Teilmengen ist NP vollständig, wenn die gewünschte Summe auch Teil der Eingabe ist. Ich will nicht, dass der Nachweis geben, wenn angefordert. Angesichts die Instanz von Teilmenge Summe {i_1, i_2, ..., i_n} zusammen mit gewünschter Summe s, erstellen Sie die folgende Instanz von VME:

{0, i_1, 0, i_2, 0, ..., i_n, s}, {+, *}, {=}

Wenn die Instanz von Teilmenge Summe auflösbar ist, dann gibt es einige Teilmenge der ganzen Zahlen, die auf 0 addiert Wenn die ganze Zahl i1 Teil der Summe ist, fügen Sie ihn mit seiner Null entspricht (unmittelbar links), und wenn i1 nicht Teil der Summe ist, es vermehren. Zwischen den einzelnen Null, und der Ausdruck auf der rechten Seite, ein Pluszeichen einfügen.

Unter der Wikipedia Beispiel

{−7, −3, −2, 5, 8}

wo { −3, −2, 5} Summen auf 0, würden wir es als

kodieren

{0, -7, 0, -3, 0, -2, 0, 5, 0, 8, 0}

und der resultierende Ausdruck wäre

{0*7 + 0 + -3 + 0 + -2 + 0 + 5 + 0*8 = 0}

Nun müssen wir auch zeigen, dass eine Lösung für diese Instanz von VME führt zu einer Lösung für die Instanz von Teilmenge Summe. Das ist einfacher, als Sie denken. Wenn wir in einem resultierenden Ausdruck betrachten, können wir Gruppe die Zahlen in solche, die mit einer 0 (als Teil einer Kette Multiplikation) multipliziert werden, und solche, die es nicht sind. Jede Zahl, die mit einer Null multipliziert wird, wird nicht in der Endsumme enthalten. Jede Zahl, die mit einer Null multipliziert wird, nicht in die endgültige Summe hinzugefügt werden müssen.

So haben wir gezeigt, dass diese Instanz von VME auflösbar ist, wenn und nur wenn die entsprechende Instanz von Teilmenge Summe ist auflösbar, so dass die Reduktion abgeschlossen ist.

EDIT: Die Partition Reduktion (mit Kommentar) arbeitet als gut und ist besser, weil es Ihnen die Gleichen überall unterschreiben setzen können. Ordentlich!

Answer 4

Sie haben die Zeit für die vollständige Antwort jetzt nicht, aber Sie können eine Reduzierung von diesem Problem auf die Knapsack Problem .

dynamische Programmierung können Sie in pseudo-Polynom Zeitlösung erreichen. Beachten Sie, dass dieses nicht Konflikt mit der Tatsache, dass das Problem in der Tat ist NP abgeschlossen.

Answer 5

Es gibt zwei Eigenschaften, die erfüllt sein müssen, damit NP auf Vollständigkeit.

Ein Entscheidungsproblem C NP-vollständig, wenn:

1. C ist in NP, und
2. Jedes Problem in NP ist reduzierbar auf C in Polynomzeit.

Wir 1. 2 ergibt sich aus der Tatsache festgestellt haben, dass jedes Problem in NP zu 3SAT und 3SAT reduzierbar ist reduzierbar auf das aktuelle Problem.

Daher ist es NP-vollständig.

(edit) Antwort auf den Kommentar unten:

Ich werde beweisen, dass SAT auf das aktuelle Problem reduzierbar ist, und da 3SAT reduzierbar auf SAT ist, folgt das Ergebnis.

Eingabeformel ist die Verbindung der folgenden Ausdrücke:

(X ₁ V x ₂ V x ₃ V ... x _n V y ₁ )

(X ₁ V x ₂ V x ₃ V ... x _n V y ₂ )

(X ₁ V x ₂ V x ₃ V ... x _n V y ₃ )

.

.

.

(X ₁ V x ₂ V x ₃ V ... x _n V y ₆₄ )

, wobei jedes y _i ein boolean ist auf das, was die Reihenfolge der zwischen dem alle x _{angewendet Operatoren i} s ist. dh y _i kann insgesamt 4x4x4x4x1 Werte annehmen (unter der Annahme, dass nur +, -, x, / sind die Betreiber und = ist immer der letzte Betreiber, das geändert werden kann, wenn der Bediener Satz geändert wird um andere Betreiber)

Falls keine der Ausdrücke wahr ist, dann ist der vollständige Ausdruck wird auf FALSCH zu bewerten, und es gibt keine Möglichkeit zu überprüfen, es sei denn, wir alle möglichen Werte ersetzen, dh x ₁ durch x _n als n Zahlen und y ₁ durch y ₆₄ , wie die verschiedenen Möglichkeiten, in denen die Operatoren angewandt werden (dies erledigt Reihenfolge)

Diese Umwandlung ist in POLY-Zeit, und die gegebene boolesche Formel ist erfüllbar genau dann, wenn der mathematische Ausdruck gültig ist, etc.

Wer einen Fehler bemerkt?

Answer 6

Das ist nicht wirklich eine Antwort auf Ihre Komplexität Frage, aber Ihr Problem klingt ein bisschen wie die http: //www.cs.nott .ac.uk / ~ gmh / countdown.pdf

Answer 7

Ich habe nicht zu Zeit einen Beweis zur Zeit zu arbeiten, aber eine Ahnung sagt mir, dass es nicht in P. sein können Sie eine Grammatik für arithmetische definieren kann, und dann diese Frage zu finden, beläuft sich auf, wenn es eine ist gültig Parse-Baum, der alle diese Terminals verwendet. i glauben , dass das Problem in NP ist, aber außerhalb von P.