Czy istnieje naturalny problem w czasie quasi-wielomianowym, ale nie w czasie wielomianowym?

21

László Babai niedawno udowodnił, że problem z izomorfizmem grafowym występuje w quasipolomomialnym czasie . Zobacz także jego przemówienie na Uniwersytecie w Chicago, notatkę z przemówień Jeremy Kun GLL post 1 , GLL post 2 , GLL post 3 .

Zgodnie z twierdzeniem LADNER, o ile PN.P. , a następnie N.P.ja nie jest pusty, to znaczy N.P. zawiera problemy, które nie są ani w P. ani N.P. -Complete. Jednak język konstruowany przez Ladnera jest sztuczny i nie stanowi naturalnego problemu. No naturalny Problem jest znany w N.P.ja nawet warunkowo pod P.N.P. . Uważa się jednak, że niektóre problemy są dobrymi kandydatami do N.P.ja , takie jak liczby całkowite faktoringu i GI.

NPQP=DTIME(npolylogn)

Istnieją pewne problemy, dla których znamy quasi-wielomianowe algorytmy czasowe, ale żaden algorytm wielomianowy nie jest znany. Takie problemy pojawiają się w algorytmach aproksymacyjnych; znanym przykładem jest ukierunkowany problem drzewa Steinera, dla którego istnieje quasi-wielomianowy algorytm aproksymacji czasu osiągający współczynnik aproksymacji ( oznacza liczbę wierzchołków). Jednak pokazanie istnienia takiego wielomianowego algorytmu czasowego jest otwartym problemem.O(log3n)n

Moje pytanie:

Czy znamy jakieś naturalne problemy, które występują w ale nie w ?QP.P.

Rupei Xu
źródło
6
Czy twierdzenie o hierarchii czasu nie gwarantuje istnienia takich problemów?
RB
@RB Dziękujemy za odpowiedź. Czy uważasz, że hierarchia czasu może się załamać? Oczekuję pewnych naturalnych przykładów, które można rozwiązać w czasie quasi-wielomianowym, ale nie w czasie wielomianowym.
Rupei Xu,
3
@RupeiXu Znany jest fakt, że nie można go zwinąć.
Tom van der Zanden,
3
@RupeiXu Twoje pytanie byłoby interesujące, jeśli szukasz naturalnego problemu.
Mohammad Al-Turkistany
3
Minimalny zestaw dominujący w turniejach to QP. Nie może być w P, chyba że ETH jest fałszywe.
Mohammad Al-Turkistany

Odpowiedzi:

25

W rzeczywistości sporo było ostatnio prac nad udowodnieniem quasi-wielomianowego czasu pracy dolnej granicy problemów obliczeniowych, opartej głównie na wykładniczej hipotezie czasowej. Oto kilka wyników dla problemów, które uważam za całkiem naturalne (wszystkie poniższe wyniki zależą od ETH):

  • Aaronson, Impagliazzo i Moshkovitz [1] wykazują dolną granicę czasu quasi-wielomianowego dla problemów z gęstym ograniczeniem (CSP). Zauważ, że sposób zdefiniowania CSP w tym dokumencie pozwala na wielomianową domenę, ponieważ wiadomo, że domena jest mała z PTAS.

  • Braverman, Ko i Weinstein [2] udowadniają dolną granicę quasi-wielomianu dla znalezienia best przybliżonej równowagi Nasha, która jest zgodna z algorytmem Liptona i wsp. [3].ϵϵ

  • Braverman, Ko, Rubinstein i Weinstein [4] pokazują dolną granicę quasi-wielomianową dla przybliżenia najgęstszego pod- wykresu z doskonałą kompletnością (tj. Biorąc pod uwagę wykres zawierający klikę, znajduje podgraph o rozmiarze który jest -dense dla niektórych małych stałych ). Ponownie istnieje quasi-wielomianowy algorytm czasu dla problemu (Feige i Seltser [5]).kkk(1ϵ)ϵ

Bibliografia

  1. AM z wieloma Merlinami. W Computational Complexity (CCC), 29. Konferencja IEEE 2014, strony 44–55, czerwiec 2014.

  2. Mark Braverman, Young Kun Ko i Omri Weinstein. Przybliżenie najlepszej równowagi Nasha w czasie -przerwa hipoteza wykładniczego czasu. W toku dwudziestego szóstego dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych, SODA '15, strony 970–982. SIAM, 2015.no(logn)

  3. Richard J. Lipton, Evangelos Markakis i Aranyak Mehta. Granie w duże gry przy użyciu prostych strategii. W Proceedings of 4th ACM Conference on Electronic Commerce, EC '03, strony 36–41, New York, NY, USA, 2003. ACM.

  4. Mark Braverman, Young Kun-Ko, Aviad Rubinstein i Omri Weinstein. Twardość ETH dla Densest- -Subgraph z doskonałą kompletnością. Electronic Colloquium on Computational Complexity (ECCC), 22:74, 2015.k

  5. U. Feige i M. Seltser. Na najgęstszych problemów -subgraph. Raport techniczny, 1997.k

Pasin Manurangsi
źródło
22

Megiddo i Vishkin udowodnił, że minimalny zestaw wyróżniającym się w turniejach w . Wykazali, że zestaw dominujący w turnieju ma algorytm czasu P, a w SAT SAT jest algorytm podwykładniczy. Dlatego problem z zestawem dominującym w turnieju nie może być w P, chyba że ETH jest fałszywe.QPP

To bardzo ciekawe, że wykładniczy hipoteza zakłada, że czas jednocześnie zestaw dominującą turniej nie może mieć wielomianowe algorytmy czas i to nie może być -CompleteNP . Innymi słowy, ETH oznacza, że zestaw wyróżniającym turniej jest w -intermediate.NP

Woeginger sugeruje rozwiązanie potencjalnego problemu w quasi-wielomianowym czasie i prawdopodobnie nie ma algorytmów wielomianowych: Czy mając liczb całkowitych, możesz wybrać log n tych, które sumują się do 0 ?nlogn0

Mohammad Al-Turkistany
źródło
10

Obliczanie wymiaru VC wydaje się mało prawdopodobne w czasie wielomianowym, ale ma algorytm quasipolynomialny.

Wydaje się również trudne do wykrycia posadzonej kliki o rozmiarze na losowym wykresie, ale można ją znaleźć w czasie quasipolynomialnym; chociaż charakter tego problemu z obietnicą jest nieco inny niż w innych wspomnianych.O(logn)

Joe Bebel
źródło
7

Jeśli hipoteza wykładniczego czasu jest poprawna (lub nawet słabsze wersje), nie można rozwiązać 3SAT dla instancji z liczbą zmiennych poligla w czasie wielomianowym. Oczywiście quasi-wielomianowy czas może łatwo rozwiązać takie przypadki.

T(n)lognT(n)T(n)

Sariel Har-Peled
źródło
2

W klasycznych algorytmach zanik korelacji i złożone zera funkcji podziału kwantowych układów wielociałowych według Arama Harrowa, Saeeda Mehrabana i Mehdiego Soleimanifara

klasyczny quasi-wielomianowy algorytm czasowy, który szacuje funkcję podziału kwantowych układów wielu ciał w temperaturach powyżej punktu przejścia fazy termicznej

jest przestawiony.

Niewiele można tu powiedzieć o części pytania „ale nie w czasie wielomianowym”. Być może nawet algorytm wielomianowy zostanie znaleziony później, biorąc pod uwagę historię poprzedniej pracy, patrz poniżej.

W jaki sposób „szacowanie funkcji podziału” związane jest z algorytmami aproksymacji? Poprzednie prace (s. 11):

Istnieje najnowsze koncepcyjnie inne podejście do szacowania funkcji podziału, które jest podstawą tej pracy. To podejście postrzega funkcję podziału jako wielowymiarowy wielowymiarowy i wykorzystuje obcięte rozwinięcie Taylora, aby rozszerzyć rozwiązanie w obliczeniowo łatwym punkcie do nietrywialnego reżimu parametrów. Od czasu jego wprowadzenia [Bar16a] tę metodę stosowano do uzyskiwania deterministycznych algorytmów dla różnych interesujących problemów, takich jak ferromagnetyczne i antyferromagnetyczne modele Isinga [LSS19b, PR18] na ograniczonych grafach.

obejmuje

[LSS19b] Jingcheng Liu, Alistair Sinclair i Piyush Srivastava. Funkcja podziału Ising: zera i przybliżenie deterministyczne. Journal of Statistics Physics, 174 (2): 287–315, 2019. arXiv: 1704.06493

który wymienia następujące w tej sekcji na temat powiązanych prac:

W równoległej linii pracy Barvinok zainicjował badanie aproksymacji Taylora logarytmu funkcji podziału, co doprowadziło do quasipolynomialnych algorytmów aproksymacji czasu dla różnych problemów zliczania [6, 7, 9, 10]. Niedawno Patel i Regts [41] wykazali, że w przypadku kilku modeli, które można zapisać jako indukowane sumy podgraficzne, faktycznie można uzyskać FPTAS z tego podejścia.

[41] V. Patel i G. Regts. Deterministyczne algorytmy aproksymacji czasu wielomianu dla funkcji podziału i wielomianów grafowych. SIAM J. Comput., 46 (6): 1893–1919, grudzień 2017. arXiv: 1607.01167

Podsumowując, „szacowanie funkcji podziału” jest ściśle związane z algorytmami aproksymacyjnymi, a dla różnych problemów zliczania istnieją algorytmy quasipolomomialnego przybliżania czasu, a dla niektórych z nich uzyskano FPTAS. Podsumowując, ta klasa problemów związanych z funkcją podziału wydaje się generować quasipolomomalne algorytmy aproksymacji czasu, ale często późniejsze ulepszenia osiągają czas wielomianowy.

Thomas Klimpel
źródło