Komplexität der Minimierung der Polynomformelgröße

28

Sei ein Grad- Polynom in Variablen über , wobei konstant ist (sagen wir 2 oder 3). Ich möchte die kleinste Formel finden , wobei „Formel“ und „Formel Größe“ sind in der offensichtlichen Weise definiert (z. B. die kleinste Formel für das Polynom ist ). $f(x_1,\dots,x_n)$ $d$ $n$ $\mathbb{F}_2$ $d$ $f$ $x_1 x_2 + x_1 x_3$ $x_1(x_2+x_3)$

Was ist die Komplexität dieses Problems - ist es NP-schwer? Hängt die Komplexität von ? $d$

[Formal ist eine Formel (auch als "arithmetische Formel" bezeichnet) ein binärer Stammbaum, dessen Blätter entweder mit einer Eingabevariablen oder der Konstante 1 gekennzeichnet sind. Alle anderen Scheitelpunkte des Baums sind mit oder . Die Größe der Formel ist die Anzahl der verwendeten Blätter. Die Formel berechnet ein Polynom rekursiv: Eckpunkte berechnen die Summe ihrer Kinder über , Eckpunkte berechnen das Produkt. ] $+$ $\times$ $+$ $\mathbb{F}_2$ $\times$

cc.complexity-theory formulas Ashley Montanaro
quelle

1

Können wir das Testen der polynomiellen Identität nicht auf dieses Problem reduzieren?

Kaveh

4

Ich denke, es gibt vielleicht eine Verbindung, aber ich sehe sie nicht sofort - insbesondere wegen der Einschränkung des Abschlusses. Außerdem wäre es interessant zu wissen, wie viel schwieriger das Problem ist, wenn es schwieriger ist als das Testen der polynomiellen Identität.

Ashley Montanaro

Wie hängt in Ihrem Fall die Anzahl der Tore (

s und

s) in der Formel mit der tatsächlichen Formelgröße zusammen? Für

scheint die Konstruktion in Ehrenfeucht und Karpinski 90 für die "gate" -Formelgröße relevant zu sein (siehe Absatz 2XOR), aber ich muss länger darüber nachdenken.

+

$+$

\times

$\times$

d = 2

$d=2$

Alessandro Cosentino

Da es sich bei der Formel um einen Binärbaum handelt, entspricht die hier verwendete Definition der Formelgröße (Anzahl der Blätter) der Anzahl der Tore (interne Eckpunkte) plus eins. Aber ich wäre auch an Ergebnissen für eine andere sinnvolle Definition der Formelgröße interessiert. Ich bin mir nicht sicher, ob ich eine Verbindung zu den Ergebnissen von Ehrenfeucht und Karpinski sehe, da es eher um die Komplexität des Zählens von Lösungen als um die Minimierung der Formelgröße geht ...

Ashley Montanaro

Um die Anzahl der Nullen zu zählen, wandeln sie zuerst die Formel in eine äquivalente um, die, wie ich mich erinnere, in Bezug auf Multiplikationen und Additionen minimal ist. Ich habe jedoch keinen Beweis für diese Minimalität. Dies würde wiederum nur den Fall

beantworten .

d = 2

$d=2$

Alessandro Cosentino

7

Sie können das co-NP-Complete TAUTOLOGY-Problem (bei einer Booleschen Formel handelt es sich um eine Tautologie?) Auf das Problem der Minimierung der Formelgröße reduzieren (da eine Formel eine Tautologie ist, wenn sie TRUE entspricht). Darüber hinaus ist TAUTOLOGY for 3DNFs (analog zu SAT for 3CNFs) co-NP-Complete.

Dana Moshkovitz
quelle

1

Wie ich die Frage verstehe, sollte

als Polynom und nicht als Funktion berechnet werden. Möglicherweise ist eine Klarstellung erforderlich.

f

$f$

Markus Bläser

3

Bei einem Grad-3-Polynom über GF (2) erfolgt eine probabilistische Reduktion von 3SAT zur Überprüfung, ob es eine Null hat [durch Betrachten zufälliger linearer Kombinationen der Klauseln], und dann von dieser zur Überprüfung, wenn ein Grad-3-Polynom vorliegt. 3 poly über GF (2), ob alles Null ist [durch Subtrahieren des Poly von 1].

Dana Moshkovitz

1

Vielen Dank! Wissen Sie, wie es mit Polynomen 2. Grades aussieht? Auch (obwohl dies wahrscheinlich sehr dicht ist) habe ich Probleme zu sehen, wie ein Grad 3-Polynom über GF (2), geschrieben in Standardform, vollständig null sein kann, ohne das Null-Polynom zu sein. Um es klar auszudrücken, stelle ich mir vor, dass die Eingabe für mein Problem eine Beschreibung des Polynoms selbst ist und nicht eine Beschreibung eines Schaltkreises, der das Polynom berechnet.

Ashley Montanaro

2

Nochmals vielen Dank für Ihre Antwort. Ich bin immer noch nicht überzeugt von der Nullsache. Es scheint mir, dass jedes n-variable Polynom über GF (2) mit Poly (n) -Termen leicht in eine Standardform umgewandelt werden kann, in der es offensichtlich ist, ob das Polynom Null ist oder nicht, indem einfach die Substitution

und Begriffe sammeln.

x^{k} \to x

$x^k \rightarrow x$

Ashley Montanaro

4

In der Tat wird ein Polynom, wenn Sie es wie beschrieben mehrlinig machen, bei jeder Eingabe zu Null ausgewertet, wenn es das Nullpolynom ist. Ein Beweis: Wählen Sie ein von Null verschiedenes Monom M mit minimalem Grad. Alle anderen Variablen auf Null setzen. Das einzige überlebende Monom ist M. Wenn Sie die Variablen in M auf 1 setzen, erhalten Sie eine Ausgabe ungleich Null.

Manu

4

Nicht genau die Antwort, aber hoffentlich hilft:

Diese Frage sollte für d = 2 bereits NP-schwer sein, wenn Sie die Minimalformel für Polynome und nicht nur für eines kennen wollen. Der Beweis ist wie folgt: Es gibt eine Eins-zu-eins-Entsprechung zwischen n bi-linearen Formeln (Formeln vom Typ ) und Tensor-3-Matrizen, dh Elementen in . Dieser Tensorrang der Matrix ist genau die Multiplikationskomplexität von n bi-linearen Formeln. $n$ $\sum a_{ij}x_iy_j$ $F_2^n\otimes F_2^n\otimes F_2^n$

Es ist bekannt, dass der Tensorrang ein NP-hartes Problem ist (wahrscheinlich ist der ungefähre Tensorrang auch NP-hart). Somit ist die Multiplikationskomplexität von bi-linearen Formeln ein NP-hartes Problem $3$ $n$

Klim
quelle

2

Vielen Dank! Dies ist eine interessante Perspektive auf das Problem.

Ashley Montanaro

Der folgende Satz hilft dabei, von vielen Polynomen zu einem Pollynom überzugehen: LEt S (f) Komplexität eines Polynoms, dann beträgt die Komplexität der Berechnung aller seiner Ableitungen höchstens 5S (f). Somit sind die Komplexitätspolynome

fast gleich der Komplexität von

f_{1}, f_{2}, \dots, f_{n}

$f_1, f_2,\ldots,f_n$

z_{1} f_{1} + z_{2} f_{2} \dots z_{n} f_{n}

$z_1f_1+z_2f_2\ldots z_n f_n$

Klim

Wenn Sie vom Tensorrang sprechen, zählen Sie nur Multiplikationen, aber keine Additionen. Der Fall

und nur eine bilineare Form ist dann einfach, da man den Rang einer bilinearen Form unter Verwendung der in Ramprasads Antwort erwähnten Struktursätze berechnen kann. (Die Beweise für diese Theoreme sind algorithmisch, siehe das Buch von Lidl & Niederreiter.)

d = 2

$d = 2$

Markus Bläser

2

Jede Antwort darauf hängt stark von dem Wortschatz ab, den Sie in der Antwort zulassen. Wenn Sie Ihre Antwort in derselben Sprache wie die Eingabe haben möchten (dh als Polynom), führt dies zu einer Reihe von Antworten, mit denen andere Poster zu kämpfen haben.

Aber wenn Sie Ihre erlauben Antwort Vokabular vergrößert werden, können wunderbare Dinge passieren. Sie können ein Beispiel in der symbolischen vs automatischen Unterscheidung sehen: In der symbolischen Unterscheidung erlaubt man nur 'Ausdrücke', die dazu neigen, ziemlich stark in die Luft zu jagen; Bei der automatischen Unterscheidung werden in der Antwort geradlinige Programme zugelassen (auch wenn die Eingabe ein Ausdruck war), was die Kontrolle der Ausdrucksschwellung erheblich erleichtert. Für univariate Polynome haben James Davenport und ich nachgedacht dass Sie zyklotomische Polynome auch als Teil Ihres Grundwortschatzes verwenden müssen (siehe die Hinweise, warum diese Polynome die einzige wirkliche Ursache für Explosionen zu sein scheinen, sowie die Artikel, die verschiedene Reduzierbarkeitsergebnisse zwischen Polynomproblemen zeigen und 3SAT).

Mit anderen Worten, wenn Sie es sich erlauben, Ihre Antwort ein wenig von der klassischen zu unterscheiden, können Sie möglicherweise nur eine andere Antwort erhalten, dh eine mit einer viel besseren Komplexität. Es hängt von Ihrer ursprünglichen Motivation ab, die Frage zu stellen, ob sie rein theoretisch oder anwendungsbezogen ist, um zu entscheiden, ob diese Variation des Wortschatzes für Sie akzeptabel ist. In der Situation, in der James und ich darüber nachgedacht haben (symbolische Berechnung), ist es vollkommen akzeptabel, das Vokabular so anzupassen, dass die Komplexität abnimmt (obwohl dies selten der Fall ist).

Jacques Carette
quelle

Die Frage fragt nach der kleinsten Rechenformel, die sie dann eindeutig definiert. Ich bin mir daher nicht sicher, ob diese Antwort direkt relevant ist. Auch die obige Antwort von Dana Moshkovitz und die zugehörigen Kommentare beantworten die Frage nicht richtig, wie bereits in den Kommentaren bestätigt.

Raphael

Der Punkt meiner Antwort ist, dass das OP möglicherweise nicht erkennt, dass es nicht unbedingt die beste Frage stellt. Die Frage des OP wird sehr klassisch gestellt, aber wenn Sie eine kleine Abweichung davon zulassen, erhalten Sie ganz andere Antworten, die möglicherweise ziemlich unerwartet waren. Ich verstehe Ihren Kommentar, finde aber, dass die Ablehnung etwas hart ist.

Jacques Carette

Könnten Sie den ersten Absatz Ihrer Antwort korrigieren, um deutlich zu machen, dass die Frage noch nicht richtig beantwortet wurde? Ich war besorgt, dass die Leute irregeführt werden könnten.

Raphael

1

@ Raffael: fertig. Und auch die Dinge weiter geklärt.

Jacques Carette

0

Die allgemeine Schaltkreis- / Formelminimierung ist sicherlich schwieriger als das Testen der Identität, da die minimale Formelgröße einer Identität einfach Null ist. Um wie viel schwieriger, ich habe keine definitive Antwort, aber vielleicht könnten die "Rekonstruktionsalgorithmen", die in arithmetischen Schaltungen / Formeln untersucht werden, etwas in diese Richtung sein.

$\mathcal{C}$ $3$ $\mathcal{C}$

$d$

$d=2$ $x_1x_2 + x_3x_4 + .. + x_{2k-1}x_{2k} + \ell$

Ramprasad
quelle

Danke für deine Kommentare. Leider verstehe ich nicht, wie ich mit diesen Ideen das ursprüngliche Problem lösen kann.

Ashley Montanaro

Komplexität der Minimierung der Polynomformelgröße

Antworten: