Lista zagadnień teoretycznych lub algebraicznych w różnych klasach złożoności

12

Szukam listy o znanej lub nieznanej złożoności różnych problemów teoretycznych / algebraicznych. Na przykład,

Adleman opublikował kiedyś listę skoncentrowaną na i N P, ale wydaje się nieaktualna. Mumford ma artykuł na temat tego, co można obliczać w geometrii algebraicznej bez względu na złożoność.PNP

Czy ktoś zna listę (głównych) odkryć od czasu opublikowania tych list?

Jakie są problemy związane z szeregiem teorii teoretycznej / algebraicznej, której klasy złożoności są prawdopodobnie znane (odkąd powyższe listy zostały opublikowane), nieznane, ale domniemane lub nieznane i nie domniemane?

Niektórymi drogami problemów mogą być problemy interpolacyjne (jedno- lub wielowymiarowe, na różnych polach), twierdzenie o chińskiej reszcie, złożoność zliczania punktów na krzywych itp.

T ....
źródło
Czy naprawdę chcesz tylko problemów, których złożoność jest nie tylko nieznana, ale nawet nie ma gdzieś spekulacji? Wydaje się to dość restrykcyjne, np. Faktoryzacja liczb całkowitych nie spełniłaby tego pytania, ponieważ spekuluje się, że znajduje się na poziomie pośrednim między P i ... Ale myślę (i mam nadzieję), że masz na myśli nieco bardziej liberalne pytanie. Ciekawie byłoby zobaczyć taką listę. UPcoUP
Joshua Grochow
@JoshuaGrochow poszerzony.
T ....
Czy wiadomo, że GCD znajduje się w obszarze dziennika?
4
Nie, jest to otwarty problem, niezależnie od tego, czy znajduje się gdziekolwiek w hierarchii NC.
Emil Jeřábek

Odpowiedzi:

18

Geometria algebraiczna

  • Lemat normalizacyjny Noether (NNL) dla wyraźnych odmian jest obecnie znany tylko w (jak ogólny NNL), ale przypuszcza się, że jest w P (i jest w P, zakładając, że PIT może być czarną skrzynką derandomizowane). Aktualizacji 18.04.18: Ostatnio wykazano, że dla różnych Ż V P jest w P S P A C E ciągu wymiernych ( Forbes i Shpilka) , a następnie na dowolnych obszarach ( Guo Saxena, i Sinhababu ).EXPSPACEPPVP¯PSPACE

  • Testowanie, czy dany zestaw wielomianów ma zależność algebraiczną. Problem ten został ostatnio wykazano, że w przez Guo, Saxena, i Sinhababu (poprawa poprzedniego górna granica N P # P powodu Mittmann, Saxena, i Scheblechner , również na arXiv ).AMcoAMNP#P

  • Istnieje kilka ( arXiv ) nowych algorytmów do obliczania topologicznych niezmienników złożonych odmian (z różnymi ograniczeniami, takimi jak gładkość itp.). Uważam, że dla większości z nich optymalna górna granica jest nadal otwarta.

  • Twierdzenie Hilberta o zerach (HN) podano całkowitą wielomianów zdecydować, czy mają wspólny złożony rozwiązanie, w zakładając GRH ( Koiran ). Nie wiadomo, czy to jest w N P .AMNP

  • Algorytmy rozwiązywania osobliwości odmian algebraicznych w charakterystycznym zera. Prąd najlepszy czas górna granica , ze względu na Bierstone, Grigoriew, Milman i Włodarczyk to , gdzie d jest wymiarem odmiany i E jest hierarchia Grzegorczyk pierwotnych funkcji rekurencyjnej . Nie ma szczególnie dobrych (żadnych?) Dolnych granic tego problemu, ale dla pozornie znacznie prostszych problemów znane są dolne granice, mianowicie: istnieją ideały w n zmiennych generowanych w stopniu co najwyżej n, które wymagają E n + 1Ed+3dEnnEn+1takie generatory. Zatem obecne górne ograniczenie rozdzielczości osobliwości może nie być dalekie od prawdy, ale tak naprawdę niewiele wiadomo.

Problemy z izomorfizmem

  • Wiele problemów dotyczących grup permutacyjnych - takich jak przecięcie cosetów, izomorfizm grup permutacyjnych itp. - dotyczy , ale nie wiadomo, czy znajdują się w N Pc o N P , i podejrzewa się, że nie są w P . Wykres Izomorfizm ogranicza się do większości tych problemów, więc lepsza górna granica implikuje lepszą górną granicę GI.NPcoAMNPcoNPP

  • W szczególności w przypadku izomorfizmu grupy permutacji obecna najlepsza górna granica wynosi , i jest otwarty, jeśli można to zrobić w czasie 2 O ( n ) (w zależności tylko od stopnia grupy permutacji, a nie od jego kolejności), nie mówiąc już o quasi-poli-czasowym, takim jak GI i przecięcie skrzyżowania .2O(n)|G|2O(n)

  • Grupa Izomorfizm gdzie grupy są przez mnożenie tabelach jest znany w , ale prawdopodobnie jest w P . Wiadomo, że w P dla kilku klas z grup (aktualizacja 18.04.18: a para ( arXiv ) więcej ( arXiv )), ale nie w ogóle.TIME(nO(logn))PP

Inny

  • Aktualizacja 18.04.18: Ranga Tensora nad dowolnym polem wynosi ∃ - F- Complete ( Schaefer & Stefankovic ). Czy ranga tensora jest wyższa niż Q w N P ? Jest wiadomo, że N P -hard ( Hastad ), a ponad określone pole to w N P .FFQNPNPNP

  • Bardziej ogólnie, wiele problemów w tensorów ponad N P -hard ale wiadomo, że w N P ( Hillar i Lim , również na arXiv ).QNPNP

Wydaje się (nieco niestety), że badanie Adlemana-McCurleya, mimo że ma 21 lat, jest dość aktualne pod względem problemów teoretycznych, z wyjątkiem faktu, że wiemy, że jest w PPRIMESP ...

Joshua Grochow
źródło
Dziwi mnie, że HN w NP jest nieznany. Wszystko, co musisz zrobić, to sprawdzić rozwiązanie dla każdego wielomianu, prawda?
T ....
I Jaka jest różnica w rozdzielczości osobliwości?
T ....
4
@Turbo: W przypadku HN wielomiany są wielomianami całkowitymi, ale rozwiązania mogą być liczbami zespolonymi, które nie muszą nawet być wyrażane przez skończoną liczbę bitów, nie mówiąc już o wielomianowej liczbie bitów. Ponadto, aby uzyskać AM, myślę, że potrzebujesz GRH.
Joshua Grochow
2
(Najpierw potwierdzam, że HN jest w AM, opiera się na GRH.) @Turbo: Dane wejściowe to zestaw liczb całkowitych, tak zdefiniowanych za pomocą skończonej liczby bitów. Oczywistym certyfikatem dla HN byłoby rozwiązanie systemu. Ale Jozue mówi, że opis takiego rozwiązania niekoniecznie można przedstawić za pomocą skończonej liczby bitów. Dlatego daleko nam do posiadania certyfikatu wielomianowego !
Bruno,
3
@Nikhil: ponieważ PIT nie określa górnej granicy NNL. Zestawy uderzeń czarną skrzynką są tym, co wiąże. Problem z wyliczaniem wszystkich możliwych zestawów uderzeń dla NNL (algorytm PSPACE dla PIT) polega na tym, że dla każdego z nich należy zweryfikować określoną właściwość, a wiadomo, że weryfikacja występuje tylko w EXPSPACE. Jeśli OTOH możesz bezpośrednio skonstruować gwarantowany zestaw uderzeń, w zasadzie nie musisz tego weryfikować. Zobaczysz, kiedy czytasz gazetę.
Joshua Grochow