Nadrzędne powody, dla których problemy występują w P lub BPP

Niedawno, rozmawiając z fizykiem, twierdziłem, że z mojego doświadczenia, kiedy problem, który naiwnie wydaje się, że powinien on zająć wykładniczy czas, okazuje się niekoniecznie w P lub BPP, „nadrzędny powód”, dla którego redukcja może być zazwyczaj zidentyfikowany --- i prawie zawsze powód ten należy do listy kilkunastu „zwykłych podejrzanych” (na przykład: programowanie dynamiczne, algebra liniowa ...). To jednak skłoniło mnie do myślenia: czy rzeczywiście możemy spisać porządną listę takich powodów? Oto pierwsza, niepełna próba jednego:

(0) Charakterystyka matematyczna. Problem ma nieoczywistą „czysto matematyczną” charakterystykę, która, gdy jest znana, natychmiast sprawia, że ​​można po prostu dokonać wyczerpującego przeszukania listy możliwości poli (n). Przykład: planarność wykresu, dla której algorytm O (n ⁶ ) wynika z twierdzenia Kuratowskiego.

(Jak wskazuje „planar” poniżej, był to zły przykład: nawet jeśli znasz kombinatoryczną charakterystykę płaskości, podanie algorytmu wielomianowego czasu jest wciąż dość nietrywialne. Pozwólcie, że podam tutaj lepszy przykład: co powiesz na powiedzmy: „biorąc pod uwagę dane wejściowe zapisane binarnie, obliczyć, ile kolorów jest potrzebnych do pokolorowania dowolnej mapy osadzonej na powierzchni za pomocą otworów n.” Z góry nie jest oczywiste, że można to w ogóle obliczyć (lub nawet skończone!). Ale istnieje znana formuła, która daje odpowiedź, a gdy ją znacie, obliczenie jej w czasie wielomianowym jest banalne. Tymczasem „sprowadza się do wykluczonych nieletnich / teorii Robertsona-Seymoura” należy prawdopodobnie dodać jako osobny nadrzędny powód, dla którego coś może być w p.)

W każdym razie nie jest to sytuacja, która najbardziej mnie interesuje.

(1) Programowanie dynamiczne. Problem można rozwiązać w sposób umożliwiający rekurencyjne rozwiązanie bez wykładniczego wybuchu - często dlatego, że ograniczenia, które należy spełnić, są ułożone liniowo lub w innej prostej kolejności. „Czysto kombinatoryczny”; nie jest wymagana struktura algebraiczna. Zapewne osiągalność wykresu (a zatem 2SAT) to przypadki szczególne.

(2) Matroidy. Problem ma strukturę matroidu, co umożliwia działanie chciwego algorytmu. Przykłady: dopasowanie, minimalne drzewo opinające.

(3) Algebra liniowa. Problem można sprowadzić do rozwiązania układu liniowego, obliczenia wyznacznika, obliczenia wartości własnych itp. Prawdopodobnie większość problemów związanych z „cudownymi anulowaniami”, w tym rozwiązanych przez formalizm zapałki Valianta, również mieści się w zakresie liniowo-algebraicznej parasolki.

(4) Wypukłość. Problem można wyrazić jako pewną wypukłą optymalizację. Programowanie półfinałowe, programowanie liniowe i gry o sumie zerowej są powszechnymi (coraz bardziej) szczególnymi przypadkami.

(5) Testowanie tożsamości wielomianowej. Problem można sprowadzić do sprawdzenia tożsamości wielomianowej, tak aby Podstawowe Twierdzenie Algebry prowadziło do wydajnego algorytmu randomizowanego - aw niektórych przypadkach, jak pierwotność, nawet algorytmu możliwego do udowodnienia.

(6) Markov Chain Monte Carlo. Problem można sprowadzić do pobierania próbek z wyniku szybko mieszającego się marszu. (Przykład: w przybliżeniu liczy się idealne dopasowanie.)

(7) Algorytm euklidesowy. GCD, ciągłe ułamki ...

Różne / Nie do końca oczywiste, jak sklasyfikować: stabilne małżeństwo, faktoring wielomianowy, problem członkostwa w grupach permutacyjnych, różne inne problemy w teorii liczb i teorii grup, problemy z siecią niskiego wymiaru ...

Moje pytanie brzmi: jakie są najważniejsze rzeczy, które pominąłem?

Wyjaśnić:

• Zdaję sobie sprawę, że żadna lista nie może być kompletna: niezależnie od skończonej liczby powodów, które podasz, ktoś będzie w stanie znaleźć egzotyczny problem w P, ale nie z żadnego z tych powodów. Częściowo z tego powodu bardziej interesują mnie pomysły, które stawiają wiele różnych, pozornie niezwiązanych problemów w P lub BPP, niż pomysły, które działają tylko na jeden problem.

• Zdaję sobie również sprawę, że subiektywne jest dzielenie rzeczy. Na przykład, czy matroidy powinny być szczególnym przypadkiem programowania dynamicznego? Czy rozwiązywanie problemu przez wyszukiwanie w pierwszej kolejności jest wystarczająco ważne, aby być jego własnym powodem, odrębnym od programowania dynamicznego? Często ten sam problem może występować w P z wielu powodów, w zależności od tego, jak na to patrzysz: na przykład znalezienie głównej wartości własnej jest w P z powodu algebry liniowej, ale także dlatego, że jest to problem optymalizacji wypukłej.

Krótko mówiąc, nie mam nadziei na „twierdzenie o klasyfikacji” - tylko na listę, która użytecznie odzwierciedla to, co obecnie wiemy o wydajnych algorytmach. I właśnie dlatego najbardziej interesują mnie techniki umieszczania rzeczy w P lub BPP, które mają szerokie zastosowanie, ale nie pasują do powyższej listy - lub inne pomysły na ulepszenie mojej prymitywnej pierwszej próby zaradzenia mojej chwale fizyk.

Niektóre klasy grafów dopuszczają algorytmy wielomianowe dla problemów trudnych NP dla klasy wszystkich grafów. Na przykład, dla idealnych wykresów, można znaleźć największy niezależny zestaw w czasie wielomianowym (dzięki vzn w komentarzu do joggingu mojej pamięci). Poprzez konstrukcję produktu pozwala to również na ujednolicone wyjaśnienie kilku pozornie całkiem różnych CSP, które można traktować (takich jak te ze strukturą drzewa, które zwykle są rozwiązywane przez rozkład hierarchiczny, i całkowicie różne ograniczenie, które zwykle rozwiązuje się przez idealne dopasowanie).

Można argumentować, że doskonałe wykresy są „łatwe”, ponieważ pozwalają na ładne sformułowania półfinałowe omawianych problemów (i dlatego podlegają algebrze liniowej i / lub wypukłości). Nie jestem jednak pewien, czy całkowicie rejestruje to, co się dzieje.

• András Z. Salamon i Peter G. Jeavons, Idealne ograniczenia są możliwe do przełknięcia, CP 2008, LNCS 5202, 524–528. doi: 10.1007 / 978-3-540-85958-1_35

• Meinolf Sellmann, The Polytope of Structured Binary Constraint Problems Satisfaction , CPAIOR 2008, LNCS 5015, 367–371. doi: 10.1007 / 978-3-540-68155-7_39

Jak zauważył Gil Kalai, właściwości grafów, które tworzą mniejsze klasy zamknięte, można zdefiniować przez skończony zestaw zabronionych nieletnich (jest to twierdzenie Robertsona-Seymour ). Kolejnym wynikiem Robertsona i Seymour jest to, że testy na obecność małoletniego można wykonać w czasie sześciennym. Razem prowadzą one do algorytmu czasu wielomianowego do decydowania o właściwościach, które są nieznacznie zamknięte.

• Neil Robertson i PD Seymour, Graph Minors. XIII Problem rozłącznych ścieżek , Journal of Combinatorial Theory, Series B 63 (1) 65–110, 1995. doi: 10.1006 / jctb.1995.1006

Jednym problemem z niewielkimi właściwościami zamkniętego wykresu jest to, że są one „małe”; wykluczenie nawet jednej nieletniej wyklucza wiele wykresów. Być może jest to jeden z powodów, dla których rozkład strukturalny Robertsona-Seymoura działa: pozostało niewiele wystarczających wykresów, aby miały ładną strukturę.

• Serguei Norine, Paul Seymour, Robin Thomas i Paul Wollan, Właściwe rodziny małoletnie zamknięte są małe , Journal of Combinatorial Theory, Series B 96 (5) 754–757, 2006. doi: 10.1016 / j.jctb.2006.01.006 ( przedruk )

Jedną próbą wyjścia poza pomniejsze klasy zamknięte są klasy zdefiniowane przez zabronione subgrafy lub zabronione indukowane subgrafy.

Właściwości wykresu zdefiniowane przez skończony zestaw zabronionych podsgrafów lub indukowanych podsgrafów można rozstrzygać w czasie wielomianowym, badając wszystkie możliwe podgrafy.

$F$$F$$F$$F$

$F$

$F$$F$$F$$F$

• Maria Chudnovsky i Paul Seymour, Z wyłączeniem indukowanych subgrafów , Ankiety w kombinatorykach 2007, 99–119, Cambridge University Press, ISBN 9780521698238. ( preprint )

$F$$F$$F$

Redukcja oparta na kratach (algorytm LLL). Jest to podstawa wydajnego wielomianowego rozkładania na czynniki całkowite i niektórych wydajnych algorytmów kryptoanalitycznych, takich jak łamanie generatorów liniowo-przystających i RSA niskiego stopnia. W pewnym sensie algorytm euklidesowy można postrzegać jako szczególny przypadek.

Programowanie liczb całkowitych Lenstry w wymiarze ograniczonym, algorytm Lenstra-Lenstra-Lovasz i powiązane kolejne algorytmy - algorytm Barvinoka dla liczby całkowitych rozwiązań problemu IP w wymiarze ograniczonym oraz algorytm P Kannana dla problemu Frobenius / Sylvester można dodać jako specjalna kategoria. Istotnym otwartym problemem tutaj jest znalezienie algorytmu P dla problemów wyższego rzędu w hierarchii Presburger.

Inną klasą algorytmu P, o której warto wspomnieć, są te algorytmy P podane obiektowi, o których udowodniono, że istnieją w losowych dowodach. Przykłady: algorytmy dla aplikacji Lovasz-Local Lemma; algorimiczne wersje wyniku niezgodności Spencera; (o nieco innym smaku) algorytmiczne wersje lematu regularności Szemeredi.

Istnieje duży i wciąż rosnący zbiór teorii na temat klas problemów związanych z ograniczeniami związanymi ze stałym szablonem, które mają algorytmy czasu wielomianowego. Wiele z tych prac wymaga opanowania książki Hobby i MacKenzie , ale na szczęście dla tych z nas, którzy bardziej interesują się informatyką niż algebrą uniwersalną, niektóre części tej teorii zostały teraz wystarczająco uproszczone, aby były dostępne dla odbiorców TCS.

$\Gamma$$S$$T$$\Gamma$$S$$T$

$\Gamma$$k \ge 3$$k$$\Gamma$$(0,0,\dots,0)$$S$$0$$T$

$\Gamma$$\Gamma$$\Gamma$$\Gamma$; oznacza to w praktyce, że klasa problemów zawiera wszystkie kolejne prostsze podproblemy rozpatrywane przez narzędzie do rozwiązywania ograniczeń, więc proces rozwiązywania ograniczeń pozwala uniknąć generowania „twardych” pośrednich instancji podczas rozwiązywania „łatwych” problemów.

$\Gamma$$\Gamma$

Dotychczasowe wyniki wydają się wskazywać, że powinna istnieć rodzaj ogólnej transformacji zasilania bazowej przestrzeni stanów osiągalności, która może przekształcić takie problemy w problemy ze stałą krotką w każdej relacji, jak w przykładzie powyżej. (To jest moja osobista interpretacja trwających badań i może być całkowicie błędna , w zależności od tego, jak trwają poszukiwania algorytmu dla algebry z cyklicznymi terminami, więc zastrzegam sobie prawo do ponownego odwołania tego.) Wiadomo, że kiedy nie ma „t , takie przekształcenie, to problem jest NP-zupełny. Granica hipotezy dychotomii polega obecnie na wypełnieniu tej luki; zobacz listę otwartych problemów z warsztatów z 2011 roku na temat algebry i CSP .

W obu przypadkach prawdopodobnie zasługuje na wpis na liście Scotta.

Druga klasa w PTIME pozwala na zastosowanie lokalnych technik spójności do przycinania możliwych rozwiązań, dopóki rozwiązanie nie zostanie znalezione lub żadne rozwiązania nie będą możliwe. Jest to zasadniczo wyrafinowana wersja sposobu, w jaki większość ludzi rozwiązuje problemy Sudoku. Nie sądzę, żeby ten powód pojawił się obecnie na liście Scotta.

$\Gamma$

Wreszcie, jest także wiele ekscytujących prac zainicjowanych przez Manuela Bodirsky'ego w przypadku domen nieskończonych. Niektóre algorytmy wyglądają dość dziwnie i mogą ostatecznie doprowadzić do większej liczby wpisów na liście Scotta.

Widzę, że Chandra o tym wspomniała, ale myślę, że struktura relaksacji LP (np. Z powodu całkowitej unimodularności) jest wszechobecną formą „struktury”, która prowadzi do wielomianowości. Odpowiada za dużą klasę algorytmów wielopoziomowych. Jeśli uwzględni się problemy z obietnicą, stanowi to także dużą klasę algorytmów aproksymacyjnych. Najczęstszymi klasami powodów, dla których można się natknąć na LP i / lub SDP, są eliminacja Gaussa i programowanie dynamiczne. Istnieją oczywiście inne, takie jak algorytmy holograficzne, które nie mają prostych wyjaśnień.