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

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

• GCD w jest otwarty,$NC^1$
• faktoring w jest otwarty,$P$
• obliczanie kohomologii snopów to -hard$\#P$ ,
• Arora i Barak stwierdzają, że wariant faktoringu jest -Complete (choć nie jest jasne, na podstawie dyskusji na NP-zupełnym wariantu faktoringu. ),$NP$
• 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ść.$P$$NP$

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.

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 ).$\mathsf{EXPSPACE}$$\mathsf{P}$$\mathsf{P}$$\overline{\mathsf{VP}}$$\mathsf{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 ).$\mathsf{AM} \cap \mathsf{coAM}$$\mathsf{NP}^{\mathsf{\# 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 .$\mathsf{AM}$$\mathsf{NP}$

• 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 + $\mathcal{E}^{d+3}$$d$$\mathcal{E}^{\bullet}$$n$$n$$\mathcal{E}^{n+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.$\mathsf{NP} \cap \mathsf{coAM}$$\mathsf{NP} \cap \mathsf{coNP}$$\mathsf{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.$\mathsf{TIME}(n^{O(\log n)})$$\mathsf{P}$$\mathsf{P}$

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 .$\mathbb{F}$$\exists \mathbb{F}$$\mathbb{Q}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

• 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 ).$\mathbb{Q}$$\mathsf{NP}$$\mathsf{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 $\mathsf{PRIMES}$$\mathsf{P}$ ...

Dodając jeszcze kilka, z naciskiem na teorię Galois i obliczeniową teorię Galois (patrz powiązane pytanie na temat cs.SE ):

$\mathbb{Z}$$\mathbb{P}$

$NP$

odtworzone z połączonego pytania na temat MO