Szukam listy o znanej lub nieznanej złożoności różnych problemów teoretycznych / algebraicznych. Na przykład,
- GCD w jest otwarty,
- faktoring w jest otwarty,
- obliczanie kohomologii snopów to -hard ,
- Arora i Barak stwierdzają, że wariant faktoringu jest -Complete (choć nie jest jasne, na podstawie dyskusji na NP-zupełnym wariantu faktoringu. ),
- Przełomowa praca Barbulescu i in. Na dyskretnych logarytmach .
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ść.
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.
Odpowiedzi:
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 ).E X P S P A C E P. P. V P¯¯¯¯¯¯¯ P S P A C E
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 ).A M ∩ c o A M N P.# 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 .M N P.
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 + 1mire+ 3 re mi∙ n n min + 1 takie 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 P ∩ c 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.N. P ∩ c o A M N. P ∩ c o N P P.
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 .2)O ( n )| G | 2)O (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.T I M E ( nO ( logn )) P. P.
Inny
Aktualizacja 18.04.18: Ranga Tensora nad dowolnym polem wynosi ∃ - F- Complete ( Schaefer & Stefankovic ).F ∃F Q NP NP NP
Czy ranga tensora jest wyższa niżQwNP?Jest wiadomo, że N P -hard ( Hastad ), a ponad określone pole to w N P .Bardziej ogólnie, wiele problemów w tensorów ponad są N P -hard ale wiadomo, że w N P ( Hillar i Lim , również na arXiv ).Q NP NP
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 PPRIMES P ...
źródło
Dodając jeszcze kilka, z naciskiem na teorię Galois i obliczeniową teorię Galois (patrz powiązane pytanie na temat cs.SE ):
odtworzone z połączonego pytania na temat MO
źródło