Problemy z dużymi otwartymi lukami złożoności

To pytanie dotyczy problemów, dla których istnieje duża otwarta luka złożoności między znaną dolną i górną granicą, ale nie z powodu otwartych problemów dotyczących samych klas złożoności.

Mówiąc ściślej, powiedzmy, że problem ma klasy przerw (z A ⊆ B , nie jednoznacznie zdefiniowane), jeśli A jest klasą maksymalną, dla której możemy udowodnić, że jest to A- twarda, a B jest minimalną znaną górną granicą , tj. mamy algorytm w B rozwiązujący problem. To znaczy, że kończy się dowiedzieć się, że problem C -Complete z A ⊆ C ⊆ B , to nie będą miały wpływ na złożoność teorii na ogół, w przeciwieństwie do znalezienia P algorytm dla N P -Complete problemu.$A,B$$A\subseteq B$$A$$A$$B$$B$$C$$A\subseteq C\subseteq B$$P$$NP$

Nie interesują mnie problemy z i B = N P , ponieważ jest to już przedmiotem tego pytania .$A\subseteq P$$B=NP$

Szukam przykładów problemów z klasami luk, które są w miarę możliwości. Aby ograniczyć zakres i uściślić pytanie, szczególnie interesują mnie problemy z i B ⊇ E X P T I M E , co oznacza, że ​​zarówno członkostwo w P, jak i E X P T I M E - kompletność jest spójna z obecną wiedzą , bez powodowania upadku znanych klas (powiedzmy, że klasy z tej listy ).$A\subseteq P$$B\supseteq EXPTIME$$P$$EXPTIME$

Knot Równoważność problem .

Biorąc pod uwagę dwa węzły narysowane w płaszczyźnie, czy są one topologicznie takie same? Problem ten jest znany jako rozstrzygalne, a tam nie wydaje się być żadnych przeszkód złożoność obliczeniowa jej istoty w P. Najlepszym górna granica obecnie wiadomo na jego złożoność czasu wydaje się, że wieża s wysokości c n , gdzie c = 10 10 6 , i n dla niektórych nowszych pokrewnych wyników i dla jawnej formy granicy, którą podałem powyżej (strona 16).$2$$c^n$$c = 10^{10^{6}}$$n$ jest liczbą skrzyżowań na schematach węzłów. Wynika to z faktu, że Coward i Lackenby powiązali liczbę ruchów Reidemeistera potrzebnych do przeniesienia jednego węzła do równoważnego. Zobacz najnowszy artykuł Lackenby'ego

Oto wersja minimalna wielkość problemu obwodu (MCSP): biorąc pod uwagę stół nieco prawdy o logicznej funkcji, to ma obwód wielkości co najwyżej 2 n / 2 ?$2^n$$2^{n/2}$

Wiadomo, że nie ma go w . Zawarte w N P . Na ogół uważa się, że N P -hard, ale jest otwarty. Uważam, że nie jest nawet znany jako A C 0 [ 2 ] - twardy. Rzeczywiście, ostatnia praca z Cody Murrayem (do pojawienia się w CCC'15) pokazuje, że nie ma jednolitej redukcji NC0 z PARITY na MCSP.$AC0$$NP$$NP$$AC0[2]$

Złożoność obliczania bitu (określonego binarnie) nieracjonalnej liczby algebraicznej (takiej jak ) jest najbardziej znaną górna granica P P P P P P P poprzez redukcję do problemu B ı t S L P których wiadomo, że ta górna granica[ABD14]. Z drugiej strony nie wiemy nawet, czy problem ten jest trudniejszy niż obliczenie parzystościnbitów - dla wszystkich wiemy, że problem może dotyczyćA C 0 . Zauważ jednak, że wiemy, że żaden automat skończony nie może obliczyć bitów nieracjonalnej liczby algebraicznej[AB07]$\sqrt{2}$$\mathsf{P^{{{PP}^{PP}}^{PP}}}$$\mathsf{BitSLP}$$n$$\mathsf{AC^0}$

Innym naturalnym problemem topologiczną, w duchu podobnym do odpowiedzi Peter Shor, znajduje twardych cząstek z 2-wymiarowych abstrakcyjnych Kompleks Symplicjalny w $\mathbb{R}^3$ . W ogóle to naturalne, aby zapytać, kiedy możemy skutecznie / efektywnie zdecydować, że streszczenie wymiarowa symplicjalnego złożone$k$ mogą być osadzone w . Dla k = 1 i D = 2, to jest płaskość wykres problemu i algorytmu liniowej czasie. Dla k = 2 i D = 2, jest również algorytm liniowego czasu . The$\mathbb{R}^d$$k=1$$d=2$$k=2$$d=2$ , d = $k=2$$d=3$ sprawa była otwarta do zeszłego roku, kiedy to Matousek, Sedgwick, Tancer i Wagner zadecydowali, że może ją rozstrzygać . Mówią, że ich algorytm ma pierwotny rekurencyjny czas, ale większy niż wieża wykładnicza . Z drugiej strony spekulują, że możliwe jest umieszczenie problemu w NP, ale wyjście poza to byłoby trudne. Wydaje się jednak, że nie ma silnych dowodów na to, że algorytm czasu policyjnego jest niemożliwy.

Ten ostatni artykuł zawiera wiele odniesień do dalszego czytania.

Automaty wielokontrowe (MCA) są automatami skończonymi wyposażonymi w liczniki, które można zwiększać i zmniejszać w ramach jednego kroku, ale przyjmować tylko liczby całkowite> = 0 jako liczby. W przeciwieństwie do maszyn Minsky'ego (inaczej automatów licznikowych) MCA nie mogą sprawdzać, czy licznik wynosi zero.

Jednym z problemów algorytmicznych z ogromną luką związaną z MSC jest problem dotyczący osiągalności. Na przykład, czy automat może osiągnąć, z konfiguracji ze stanem początkowym i wszystkimi licznikami zerowymi, konfiguracją ze stanem akceptacji i wszystkimi licznikami ponownie.

Problem jest trudny dla EXPTIME (jak wykazał Richard Lipton w 1976 r.), Możliwy do rozstrzygnięcia (Ernst Mayr, 1981) i rozwiązany w Fω3 (dzięki, Sylvain, za zwrócenie na to uwagi). Ogromna luka.

$\mathsf{QMA}(2)$ (Quantum Merlin-Arthur with two unentangled provers): certainly $\mathsf{QMA}$-hard, but only known to be in $\mathsf{NEXP}$.

The computational problem associated to Noether's Normalization Lemma for explicit varieties ("explicit" in the sense of this paper [freely available full version]). Best known upper bound is $\mathsf{EXPSPACE}$ (note, SPACE, not TIME!) but it is conjectured to be in $\mathsf{P}$ (and indeed, its being in $\mathsf{P}$ is essentially equivalent to derandomizing PIT).

The Skolem problem (given a linear recurrence with integer base cases and integer coefficients, does it ever reach the value 0) is known to be NP-hard and not known to be decidable. As far as I know anything in between would be consistent with our current knowledge without any collapses of standard complexity classes.