Złożoność minimalizowania wielkości formuły wielomianowej

28

Niech jest stopień wielomian zmienne przez , w którym jest stała (przykładowo 2 lub 3). Chciałbym znaleźć najmniejszą formułę dla , gdzie „formuła” i „rozmiar formuły” są zdefiniowane w oczywisty sposób (np. Najmniejsza formuła dla wielomianu to ). $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)$

Jaka jest złożoność tego problemu - czy jest NP-trudny? Czy złożoność zależy od ? $d$

[Bardziej formalnie, formuła (inaczej „formuła arytmetyczna”) jest ukorzenionym drzewem binarnym, z którego każdy liść jest oznaczony albo zmienną wejściową, albo stałą 1. Wszystkie pozostałe wierzchołki drzewa są oznaczone lub . Rozmiar formuły to liczba użytych liści. Formuła oblicza wielomian rekurencyjnie: wierzchołki obliczają sumę swoich dzieci względem , wierzchołki obliczają iloczyn. ] $+$ $\times$ $+$ $\mathbb{F}_2$ $\times$

cc.complexity-theory formulas Ashley Montanaro
źródło

1

czy nie możemy zredukować testowania tożsamości wielomianowej do tego problemu?

Kaveh,

4

Myślę, że może istnieć związek, ale nie widzę go od razu - w szczególności z powodu ograniczenia stopnia. Poza tym, jeśli problem jest trudniejszy niż testowanie tożsamości wielomianowej, interesujące byłoby wiedzieć, o ile trudniejsze.

Ashley Montanaro,

W twoim przypadku, w jaki sposób liczba bramek (

si

s) w formule jest powiązana z faktycznym rozmiarem formuły? Dla

konstrukcja Ehrenfeuchta i Karpińskiego 90 wydaje się mieć znaczenie (patrz akapit 2XOR) dla rozmiaru „bramki”, ale muszę o tym dłużej myśleć.

+

$+$

\times

$\times$

d = 2

$d=2$

Alessandro Cosentino

Ponieważ formuła jest drzewem binarnym, zastosowana tutaj definicja wielkości formuły (liczba liści) jest równa liczbie bramek (wewnętrzne wierzchołki) plus jeden. Byłbym jednak zainteresowany wszelkimi wynikami dla każdej innej rozsądnej definicji rozmiaru formuły. Nie jestem pewien, czy widzę związek z wynikami Ehrenfeuchta i Karpińskiego, ponieważ dotyczą one złożoności rozwiązań zliczających, a nie minimalizują rozmiar formuły ...

Ashley Montanaro

d = 2

$d=2$

7

Możesz zredukować problem TAUTOLOGII współpełniającej NP (biorąc pod uwagę formułę logiczną, czy jest to tautologia?) Do problemu minimalizacji wielkości formuły (ponieważ formuła jest tautologią i jest odpowiednikiem PRAWDA). Co więcej, TAUTOLOGIA dla 3DNF (analogicznie do SAT dla 3CNF) jest co-NP-Complete.

Dana Moshkovitz
źródło

1

f

$f$

3

Występuje probabilistyczna redukcja z 3SAT do sprawdzania, biorąc pod uwagę wielomian deg-3 w stosunku do GF (2), czy ma zero [przez losowe liniowe kombinacje klauzul], a następnie z tego do sprawdzania, biorąc pod uwagę deg- 3 poli ponad GF (2), niezależnie od tego, czy jest całkowicie zerowy [przez odjęcie poli od 1].

Dana Moshkovitz

1

Dzięki! Czy masz pojęcie, jak wygląda sytuacja w przypadku wielomianów stopnia 2? Ponadto (choć jest to prawdopodobnie bardzo gęsta) staram się zobaczyć, jak wielomian stopnia 3 nad GF (2), zapisany w standardowej formie, może być zerowy, nie będąc wielomianem zerowym. Dla jasności wyobrażam sobie, że wkładem do mojego problemu jest opis samego wielomianu, a nie opis obwodu obliczającego wielomian.

Ashley Montanaro,

2

x^{k} \to x

$x^k \rightarrow x$

4

Rzeczywiście, jeśli uczynisz ją wieloliniową, tak jak to opisano, wielomian ocenia się na zero na każdym wejściu, jeśli jest to wielomian zero. Jeden dowód: wybierz niezerowy jednomian M o minimalnym stopniu. Ustaw na zero wszystkie inne zmienne. Jedynym zachowanym monomialem jest M. Ustawiając zmienne w M na 1, otrzymujesz niezerową moc wyjściową.

Manu,

4

Nie do końca odpowiedź, ale mam nadzieję, że pomaga:

$n$ $\sum a_{ij}x_iy_j$ $F_2^n\otimes F_2^n\otimes F_2^n$

$3$ $n$

Klim
źródło

2

Dzięki! To ciekawe spojrzenie na problem.

Ashley Montanaro,

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$

d = 2

$d = 2$

2

Każda odpowiedź na to pytanie zależy w ogromnym stopniu od słownictwa, na które pozwalasz w odpowiedzi. Jeśli chcesz uzyskać odpowiedź w tym samym języku co dane wejściowe (tj. Wielomian), prowadzi to do jednego zestawu odpowiedzi, z którym zmagają się inni plakaty.

Ale jeśli pozwolisz na poszerzenie słownika odpowiedzi , mogą się zdarzyć cudowne rzeczy. Możesz zobaczyć przykład w różnicowaniu symbolicznym vs automatycznym: w różnicowaniu symbolicznym dopuszcza się tylko „wyrażenia”, które mają tendencję do bardzo gwałtownego wybuchu; w automatycznym różnicowaniu dopuszcza się programy proste w odpowiedzi (nawet jeśli dane wejściowe były wyrażeniem), co znacznie pomaga kontrolować wzrost wyrażenia. James Davenport i ja zastanawialiśmy się nad wielomianami jednowymiarowymi że musisz wrzucać wielomiany cyklotomiczne również w ramach podstawowego słownictwa (zobacz odniesienia do tego, dlaczego te wielomiany wydają się jedynym prawdziwym źródłem wysadzenia w powietrze, a także dokumenty, które pokazują różne wyniki pomniejszenia między problemami wielomianowymi i 3SAT).

Innymi słowy, jeśli pozwolisz sobie na zmianę nieco tego, co uważasz za odpowiedź nieco od klasycznej, możesz być w stanie uzyskać raczej inną odpowiedź, tj. O znacznie większej złożoności. To zależy od twojej pierwotnej motywacji, by zadać pytanie, czy to czysto teoretyczne, czy z myślą o aplikacji, aby zdecydować, czy ta różnorodność słownictwa jest dla Ciebie akceptowalna. W otoczeniu, w którym James i ja myśleliśmy o tym (obliczenia symboliczne), dostosowanie słownictwa tak, aby spadek złożoności był całkowicie akceptowalny (choć rzadko robiony).

Jacques Carette
źródło

Pytanie dotyczy najmniejszej formuły arytmetycznej, którą następnie jasno określa. Nie jestem zatem pewien, czy ta odpowiedź jest bezpośrednio istotna. Ponadto powyższa odpowiedź Dany Moshkovitz i powiązane komentarze nie odpowiadają poprawnie na pytanie, co zostało już potwierdzone w komentarzach.

Raphael

Chodzi mi o to, że PO może nie zdawać sobie sprawy, że niekoniecznie zadaje najlepsze pytanie. Pytanie OP jest zadawane w bardzo klasyczny sposób, ale jeśli pozwolisz na małe odchylenie od tego, otrzymasz zupełnie inne odpowiedzi, co może być dość nieoczekiwane. Rozumiem twój komentarz, ale uważam, że głosowanie jest trochę surowe.

Jacques Carette,

Czy możesz poprawić pierwszy akapit swojej odpowiedzi, aby wyjaśnić, że pytanie nie zostało jeszcze poprawnie udzielone? Martwiłem się, że ludzie mogą być wprowadzani w błąd.

Raphael

1

@Raphael: gotowe. I wyjaśniłem też dalej.

Jacques Carette,

0

Ogólne minimalizowanie obwodu / formuły jest z pewnością trudniejsze niż testowanie tożsamości, ponieważ minimalny rozmiar formuły dowolnej tożsamości wynosi po prostu zero. Co do tego, o ile trudniejsze, nie mam ostatecznej odpowiedzi, ale być może „algorytmy rekonstrukcji” badane w obwodach / formułach arytmetycznych mogą być czymś podobnym.

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

$d$

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

Ramprasad
źródło

Dziękuję za komentarze. Niestety nie wiem, jak wykorzystać te pomysły do rozwiązania pierwotnego problemu.

Ashley Montanaro,

Złożoność minimalizowania wielkości formuły wielomianowej

Odpowiedzi: