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

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 $P \neq NP$ , a następnie $NPI$ nie jest pusty, to znaczy $NP$ zawiera problemy, które nie są ani w $P$ ani $NP$ -Complete. Jednak język konstruowany przez Ladnera jest sztuczny i nie stanowi naturalnego problemu. No naturalny Problem jest znany w $NPI$ nawet warunkowo pod $P \neq NP$ . Uważa się jednak, że niektóre problemy są dobrymi kandydatami do $NPI$ , takie jak liczby całkowite faktoringu i GI.

$NP \not\subseteq QP = DTIME(n^{poly\log n})$

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(\log^3 n)$$n$

Moje pytanie:

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

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].$\epsilon$$\epsilon$

• 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]).$k$$k$$k$$(1 - \epsilon)$$\epsilon$

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.$n^{o(log n)}$

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$

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.$QP$$P$

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ć -Complete$NP$ . 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 ?$n$$\log n$$0$

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(\log n)$

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 ) * \log n$$T(n)$$T(n)$

Ostatnio pokazano, że gry Solving Parity są w QP: https://www.comp.nus.edu.sg/~sanjay/paritygame.pdf

$\mu$

$NP\cap coNP$$UP\cap coUP$

Jednak ostatni artykuł powyżej znacznie skoczył do QP. Nadal nie wiadomo, czy te gry są w P.

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.