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

32

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,BABAABBCACBPNP

Nie interesują mnie problemy z i B = N P , ponieważ jest to już przedmiotem tego pytania .APB=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 ).APBEXPTIMEPEXPTIME

Denis
źródło
Co rozumiesz przez klasy problemu? Załóżmy, że problemem jest SAT, jak definiujesz klasy?
RB
SAT jest NP-kompletny, więc możemy przyjąć i nie ma tutaj przerwy, ponieważ złożoność SAT pasuje dokładnie do już dobrze znanej klasy. Pokazanie jakiegokolwiek nowego wyniku złożoności SAT (mianowicie przynależności do mniejszej klasy) byłby przełomem w teorii złożoności. To prawda, że ​​pytanie nie jest całkowicie dobrze zdefiniowane, ponieważ zależy od tego, które klasy złożoności są uważane za „główny nurt”, a A , B nie są jednoznacznie zdefiniowane. Szczegółowe pytanie jest jednak dobrze zdefiniowane: przykłady języków, dla których jest spójne z obecną wiedzą, że są w P lub EXPTIME-zupełne. A=B=NPA,B
Denis,
właściwie wciąż nie jest do końca dobrze zdefiniowany z powodu „nieupadania się”, więc opiera się na pojęciu „dobrze znanej klasy”. Oczywiście problem z kompletnym PSPACE nie spełnia tego wymagania, chociaż bycie w P lub EXPTIME-complete jest spójne z obecną wiedzą. Na przykład ta lista może być wykorzystana jako odniesienie do „dobrze znanej” klasy: en.wikipedia.org/wiki/List_of_complexity_classes
Denis
13
Nie do końca pasuje do twojego konkretnego pytania, ale pod każdym względem egzystencjalna teoria reali uparcie opiera się wszelkim dalszym klasyfikacjom poza byciem twardym NP i w ramach PSPACE (to ostatnie według wyniku JF Canny'ego z 1988 roku). en.wikipedia.org/wiki/Existential_theory_of_the_reals
zawilec

Odpowiedzi:

28

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).2cnc=10106n 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

Peter Shor
źródło
Dziękuję za Twoją odpowiedź. Czy znasz obecne granice? Czy możesz wskazać odniesienie stwierdzające aktualny stan wiedzy? Mam problem ze znalezieniem jasnego.
Denis,
Próbowałem znajdź coś więcej niż 1998 niedawnej papierze Hass, Lagarias i Pippenger tutaj . Stwierdza to, że problem równoważności węzła jest znany jako rozstrzygalny. Nie zdziwiłbym się, gdyby ktoś pokazał, że od tego czasu jest w EXPTIME, ale nie wierzę w nic lepszego niż to, co jest znane, i na pewno nie jest jasne, że nie ma w P. Nie jestem pewien, że żaden wyników pokazujących, że podejmowanie decyzji, czy coś jest wiązane, leży w NP i dotyczy tego bardziej ogólnego problemu.
Peter Shor
To pytanie MO jest powiązane: mathoverflow.net/questions/77786/... W szczególności, korzystając z najnowszych wyników ogłoszonych przez Lackenby w people.maths.ox.ac.uk/lackenby/ekt11214.pdf , można uzyskać, że dla dowolnego węzła typu K, ustalenie, czy dany węzeł jest równoważny K, jest wyrażone w NP (zauważ, że to nie poprawia się w przypadku problemu równoważności węzła)
Arnaud
@Arnaud: w rzeczywistości, to wygląda mi na to, wyniki te dowodzą, że dla dwóch schematów z co najwyżej n przejściach, Knot Równoważność Problem może być rozwiązany w czasie co najwyżej wieży 2 w wysokości , gdzie c jest ogromny stałą . Powinienem to sprawdzić i edytować swoją odpowiedź. cnc
Peter Shor
@PeterShor Tak, rzeczywiście. Skupiłem się na najnowszym wyniku, ponieważ może to prowadzić do lepszego wiązania po opublikowaniu, jeśli zostanie wyjaśniony faktyczny wielomian.
Arnaud
23

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 ?2n2n/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.AC0NPNPAC0[2]

Ryan Williams
źródło
23

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]2PPPPPPPBitSLPnAC0

SamiD
źródło
21

Innym naturalnym problemem topologiczną, w duchu podobnym do odpowiedzi Peter Shor, znajduje twardych cząstek z 2-wymiarowych abstrakcyjnych Kompleks Symplicjalny w R3 . W ogóle to naturalne, aby zapytać, kiedy możemy skutecznie / efektywnie zdecydować, że streszczenie wymiarowa symplicjalnego złożonek 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 . TheRdk=1d=2k=2d=2 , d = 3k=2d=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.

Sasho Nikolov
źródło
16

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.

Thomas S.
źródło
3
Cześć Thomas, w ostatnim artykule arXiv istnieje roszczenie o wyraźnej (i najprawdopodobniej nie wąskiej) złożoności: arxiv.org/abs/1503.00745 . Proponowana górna granica wfaω3)jest jednak daleko poza klasami złożoności, którymi był zainteresowany oryginalny plakat.
Sylvain
@Sylvain Cool! Dzięki za udostępnienie tego. :)
Michael Wehar,
@Sylvain Czy EXPTIME jest najbardziej znaną dolną granicą?
Michael Wehar,
2
@Michael: the best lower bound on the decision problem is actually EXPSPACE (Lipton, 1976, cpsc.yale.edu/sites/default/files/files/tr63.pdf). However, the algorithm by Mayr (1981, dx.doi.org/10.1145/800076.802477), Kosaraju (1982, dx.doi.org/10.1145/800070.802201), and Lambert (1992, dx.doi.org/10.1016/0304-3975(92)90173-D) analysed in the mentioned arXiv paper is known to require at least Ackermannian (i.e., Fω) time.
Sylvain
@Sylvain Thank you very much for all of the additional information. I really appreciate it. :)
Michael Wehar
11

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

Martin Schwarz
źródło
9

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 EXPSPACE (note, SPACE, not TIME!) but it is conjectured to be in P (and indeed, its being in P is essentially equivalent to derandomizing PIT).

Joshua Grochow
źródło
Can you provide more info on this in an explicit form? looks like some kind of bpp-complete problem?
@Arul: Neither PIT nor this problem is BPP-complete in any sense that I am aware of. (In fact, showing that BPP-complete problems exist is still open, and requires non-relativizing techniques - a result going back to Sipser.) However, derandomizing either has a hardness-randomness trade-off, in that their derandomization is essentially equivalent to lower bounds. Aside from the paper linked in the answer ("GCT 5"), lookup hardness-randomness and Kabanets-Impagliazzo.
Joshua Grochow
I will do that but I was interested in this phrase 'and indeed, its being in P is essentially equivalent to derandomizing PIT' which seems to say PIT is some kind of proxy complete problem
@Arul: Yes, to see why PIT is such a "proxy complete problem," see the things I referred to in my previous comment.
Joshua Grochow
why does he use 'Dedicated to Sri Ramakrishna' in many of his works?
6

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.

David Eppstein
źródło