Główne nierozwiązane problemy w informatyce teoretycznej?

Wikipedia wymienia tylko dwa problemy w kategorii „nierozwiązane problemy w informatyce” :

• P = NP?
• Istnienie funkcji jednokierunkowych

Jakie są inne poważne problemy, które należy dodać do tej listy?

Zasady:

1. Tylko jeden problem na odpowiedź
2. Podaj krótki opis i wszelkie odpowiednie linki

Czy w operacjach można wykonać mnożenie przez macierzy ?n O ( n 2$n$$n$$O(n^2)$

Wykładnik najlepiej znanej górnej granicy ma nawet specjalny symbol . Obecnie wynosi około 2,376 według algorytmu Coppersmith-Winograd . Ładny przegląd stanu techniki to Sara Robinson, W stronę optymalnego algorytmu mnożenia macierzy , SIAM News, 38 (9), 2005.$\omega$$\omega$

Aktualizacja: Andrew Stothers (w swojej rozprawie z 2010 r. ) Wykazał, że , którą poprawiła Virginia Vassilevska Williams (w przedruku z lipca 2014 r. ) Do . Oba te granice uzyskano poprzez dokładną analizę podstawowej techniki Coppersmitha-Winograda.ω < $\omega < 2.3737$$\omega < 2.372873$

Dalsza aktualizacja (30 stycznia 2014 r.): François Le Gall udowodnił, że w artykule opublikowanym w ISSAC 2014 ( preprint arXiv ).$\omega < 2.3728639$

Czy wykres izomorfizmu w P?

Złożoność izomorfizmu grafowego (GI) jest kwestią otwartą od kilku dziesięcioleci. Stephen Cook wspomniał o tym w swoim artykule z 1971 roku na temat kompletności NP dla SAT .

Ustalenie, czy dwa wykresy są izomorficzne, można zwykle zrobić szybko, na przykład za pomocą oprogramowania takiego jak nautyi saucy. Z drugiej strony Miyazaki skonstruował klasy instancji, dla których możliwe jest, nautyże wykładniczy czas.

Przeczytaj i Corneil dokonał przeglądu wielu prób rozwiązania złożoności GI do tego momentu: The Graph Isomorphism Disease , Journal of Graph Theory 1 , 339–363, 1977.

Nie wiadomo, że GI występuje w ko-NP, ale istnieje prosty randomizowany protokół dla Graph Non-Isomorphism (GNI). Dlatego uważa się, że GI (= co-DNB) jest „bliskie” NP co-NP.${}\cap{}$

Z drugiej strony, jeśli GI jest kompletne NP, wówczas hierarchia wielomianowa się zapada. Jest więc mało prawdopodobne, aby GI było kompletne NP. (Boppana, Håstad, Zachos, Czy co-NP ma krótkie interaktywne dowody?, IPL 25 , 127–132, 1987)

Shiva Kintali ma fajną dyskusję na temat złożoności GI na swoim blogu.

Laszlo Babai udowodnił, że izomorfizm grafów odbywa się w czasie podwykonawczym .

Złożoność faktoringu

Czy faktoring jest w ?$\mathsf{P}$

• Konsekwencje faktoringu w P?
• Czy problemy PRIMES, FACTORING są znane jako P-hard?
• Jakie są konsekwencje faktoringu jako NP-complete?
• P z wyrocznią z faktoryzacji całkowitej
• Dowody na faktoryzację liczb całkowitych podano w P (w MO )

P = BPP?

Czy istnieje reguła przestawna dla algorytmu simpleks, która zapewnia wielomian najgorszego przypadku? Mówiąc bardziej ogólnie, czy istnieje algorytm silnie wielomianowy do programowania liniowego?

Wykładniczego w czasie hipotezy (ETH) potwierdza, że rozwiązanie SAT wymaga wykładniczy, 2 ^{Ω (n)} w czasie. ETH implikuje wiele rzeczy, na przykład, że SAT nie jest w P, więc ETH implikuje P ≠ NP. Zobacz Impagliazzo, Paturi, Zane, Które problemy mają silnie wykładniczą złożoność? , JCSS 63, 512–530, 2001.

Powszechnie uważa się, że ETH jest trudny do udowodnienia, ponieważ implikuje wiele innych separacji klas złożoności.

Immerman i Vardi pokazują, że logika stałoprzecinkowa przechwytuje PTIME w klasie uporządkowanych struktur. Jednym z największych otwartych problemów w opisowej teorii złożoności jest to, czy można usunąć zależność od kolejności:

Czy istnieje logika, która przechwytuje PTIME?

Mówiąc prościej, logika przechwytująca PTIME jest językiem programowania dla problemów z grafem, który działa bezpośrednio na strukturze wykresu i nie ma dostępu do kodowania wierzchołków i krawędzi, co powoduje, że:

1. każdy poprawny składniowo program modeluje problem graficznego obliczania czasu wielomianowego i
2. każdy problem z grafem obliczalnym w czasie wielomianowym można modelować za pomocą poprawnego składniowo programu.

Jeśli nie ma logiki przechwytującej PTIME, to ponieważ NP jest przechwytywana przez egzystencjalną logikę drugiego rzędu. Logika przechwytująca PTIME zapewniłaby możliwy atak na P vs NP.$P \neq NP$

Zobacz blog Lipton jest dla nieformalnej dyskusji i M. Grohe: Quest for logika Przechwytywanie PTIME (LIC 2008) do badania bardziej technicznej.

Czy przypuszczenie, że unikalne gry są prawdziwe?
I: Biorąc pod uwagę, że istnieją algorytmy przybliżania podwykładniczego czasu dla unikalnych gier , gdzie ostatecznie problem leży w zakresie złożoności krajobrazu?

Stałe kontra Determinant

Pytanie stałe kontra decydujące jest interesujące ze względu na dwa fakty. Po pierwsze, stała macierzy zlicza liczbę idealnych dopasowań na grafie dwustronnym. Dlatego stałą takiej macierzy jest # P-Complete. Jednocześnie definicja stałej jest bardzo zbliżona do definicji wyznacznika, ostatecznie różna tylko z powodu prostej zmiany znaku. Obliczenia determinantowe są dobrze znane w P. Badanie różnicy między wyznacznikiem trwałym a wyznacznikiem oraz ile obliczeń wyznacznikowych jest wymaganych do obliczenia stałego mówienia o P w funkcji #P.

Czy możemy obliczyć FFT w czasie krótszym niż ?$O(n \log n)$

W tym samym (bardzo) ogólnym sensie istnieje wiele pytań dotyczących poprawy czasów działania wielu klasycznych problemów lub algorytmów: np. Czy wszystkie pary najkrótszych ścieżek (APSP) można rozwiązać w czas?$O(n^{3-\epsilon})$

Edycja: APSP działa w czasie ”, gdzie dodawanie i porównywanie wartości rzeczywistych jest kosztem jednostkowym (ale wszystkie inne operacje mają typowe koszt logarytmiczny) ”: http://arxiv.org/pdf/1312.6680v2.pdf$(\frac{n^3}{2^{\Omega(log n)^{1/2}}})$

Dynamiczny optymalność przypuszczenie dla drzew splay.

Lub bardziej ogólnie: czy jakieś drzewo dynamicznego wyszukiwania binarnego online O (1) jest konkurencyjne?

Algorytm deterministyczny czasu liniowego dla problemu minimalnego drzewa opinającego.

NP kontra co-NP

Pytanie NP a co-NP jest interesujące, ponieważ NP ≠ co-NP implikuje P ≠ NP (ponieważ P jest zamknięte pod dopełniaczem). Odnosi się także do „dualności”: separacji między znajdowaniem / weryfikowaniem przykładów a znajdowaniem / weryfikowaniem kontrpróbek. W rzeczywistości udowodnienie, że pytanie dotyczy zarówno NP, jak i co-NP, jest naszym pierwszym dobrym dowodem na to, że problem, który wydaje się być poza P, prawdopodobnie również nie jest NP-Complete.

Czy istnieją problemy, których nie można skutecznie rozwiązać za pomocą komputerów równoległych?

Problemy, które są P-pełne, nie są znane jako możliwe do zrównoleglenia. Problemy z P-complete obejmują Horn-SAT i programowanie liniowe. Ale udowodnienie, że tak jest, wymagałoby oddzielenia pewnej koncepcji problemów możliwych do zrównoleglenia (takich jak NC lub LOGCFL) z P.

Konstrukcje procesorów komputerowych zwiększają liczbę jednostek przetwarzających w nadziei, że poprawi to wydajność. Jeżeli podstawowych algorytmów, takich jak programowanie liniowe, z natury nie można zrównoleglać, wówczas występują znaczące konsekwencje.

Czy wszystkie tautologie zdań mają wielomianowe dowody Frege?

Prawdopodobnie główny otwarty problem złożoności dowodu : zademonstruj super-wielomianowe dolne granice na dowodach zdań (zwanych również dowodami Frege'a).

Nieoficjalnie, system Frege proof jest tylko standardowym systemem dowodzenia zdań do dowodzenia tautologii zdań (jeden uczy się w podstawowym kursie logicznym), mającym aksjomaty i reguły dedukcyjne, w których linie dowodu są zapisywane jako formuły. Rozmiar dowodu Frege jest liczba symboli trzeba spisać dowód.

Następnie pojawia się pytanie, czy istnieje rodzina formuł tautologicznych zdań, dla których nie ma wielomianu tak że minimalny rozmiar w wynosi co najwyżej , dla wszystkich (gdzie oznacza rozmiar formuły ).$(F_n)_{n=1}^\infty$$p$$F_n$$p(|F_n|)$$n=1,2,\ldots$$|F_n|$$F_n$

Formalna definicja systemu zabezpieczenia Frege

Definicja (Frege zasada) ± zasada Frege jest sekwencją propozycjonalnych wzorach dla , napisany w . W przypadku reguła Frege nazywa się schematem aksjomatycznym . się, że formuła pochodzi z reguły z jeśli są instancjami podstawienia , dla pewnego przypisania do zmiennych (to znaczy istnieją formuły $A_0(\overline x),\ldots,A_k(\overline x)$$k \le 0$$\frac{A_1(\overline x), \ldots,A_k(\overline x)}{A_0(\overline x)}$$k = 0$$F_0$$F_1,\ldots,F_k$$F_0,\ldots,F_k$$A_1,\ldots,A_k$$\overline x$$B_1,\ldots,B_n$ takie, że dla wszystkich . Zasada Frege mówi się dźwięku jeśli gdy zadanie spełnia formuły w górnej bocznej , a także spełnia wzór w dolnej bocznej .$F_i = A_i(B_1/x_1,\ldots,B_n/x_n),$$i=0,\ldots,k$$A_1,\ldots,A_k$$A_0$

Definicja (dowód Frege'a) Biorąc pod uwagę zestaw reguł Frege'a, dowód Frege'a jest ciągiem formuł takich, że każda linia dowodu jest albo aksjomatem, albo pochodzi z jednej z podanych reguł Frege'a z poprzednich linii dowodu. Jeśli sekwencja kończy o wzorze , a dowodem jest uważane za dowód . Wielkość dowodu Frege jest całkowite rozmiary wszystkich preparatów w dowodzie.$A$A$A$

System dowód mówi się implicationally kompletna , jeśli dla każdego zestawu wzorach , jeśli semantycznie oznacza , to jest dowodem stosując (ewentualnie) axioms z . Mówi się, że system dowodowy jest solidny, jeśli dopuszcza dowody tylko tautologii (gdy nie stosuje się aksjomatów pomocniczych, jak w powyższym ).$T$$T$$F$$F$$T$$T$

Definicja (system zabezpieczenia Frege'a) Biorąc pod uwagę język zdań i skończony zestaw reguł dźwięku Frege, mówimy, że jest systemem zabezpieczenia Frege, jeśli jest domyślnie kompletny.$P$$P$P$P$

Pamiętaj, że dowód Frege jest zawsze prawidłowy, ponieważ zakłada się, że reguły Frege są prawidłowe. Nie musimy pracować z konkretnym systemem dowodu Frege, ponieważ podstawowy wynik w złożoności dowodu stwierdza, że ​​każde dwa systemy dowodu Frege, nawet w różnych językach, są wielomianowo równoważne [Reckhow, praca doktorska, University of Toronto, 1976].

Ustalenie dolnych granic dla dowodów Frege'a może być postrzegane jako krok w kierunku udowodnienia , ponieważ jeśli jest to prawdą, to żaden system dowodu propozycyjnego (w tym Frege) nie może mieć wielomianowych dowodów wielkości dla wszystkich tautologii.$NP \neq coNP$

Czy możemy obliczyć odległość edycji między dwoma łańcuchami długości czasie podkwadratowym, tj. W czasie dla niektórych ?O ( n 2 - ϵ ) ϵ > $n$$O(n^{2-\epsilon})$$\epsilon>0$

Czy istnieją naprawdę algorytmy czasu subkwadratowego (co oznacza czas dla jakiejś stałej ) dla problemów trudnych 3SUM ?$O(n^{2-\delta})$$\delta>0$

W 2014 r. Grønlund i Pettie opisali algorytm deterministyczny dla samego 3SUM, który działa w czasie . Chociaż jest to istotny wynik, poprawa w stosunku do jest jedynie (sub) logarytmiczna. Co więcej, nie są znane podobne algorytmy subkwadratowe dla większości innych problemów trudnych 3SUM.$O(n^2/(\log n/\log \log n)^{2/3})$$O(n^2)$

BQP = P?

Również: NP zawarte w BQP?

Wiem, że naruszyło to zasadę, mając dwa pytania w odpowiedzi, ale kiedy są wzięte z pytaniem P vs NP, niekoniecznie są to pytania niezależne.

1. Hipoteza izomorfizmu. (Czy wszystkie problemy NP-zupełne są „tym samym” problemem?)
2. Czy kryptografia może być oparta na problemie NP-zupełnym?

i nieco dalej od głównego nurtu:


3. Jaki jest rozmiar NP w ramach EXP?

(Nieoficjalnie, jeśli masz wszystkie problemy z EXP na stole i losowo wybierasz jeden równomiernie, jakie jest prawdopodobieństwo, że wybrany problem występuje również w NP? To pytanie zostało sformalizowane przez pojęcie miary ograniczonej do zasobów Wiadomo, że P ma miarę zerową w ramach EXP, tzn. Problem, który wychwyciłeś z tabeli, prawie na pewno nie występuje w P.)

Jaka jest przybliżalność metrycznego TSP ? Algorytm Christofidesa z 1975 roku jest algorytmem aproksymacji czasu wielomianowego (3/2). Czy NP jest trudniejszy do zrobienia lepiej?

• Przybliżenie metrycznego TSP do współczynnika mniejszego niż 220/219 jest NP-twarde (Papadimitriou i Vempala, 2006 [PS] ). Według mojej wiedzy jest to najbardziej znana dolna granica.

• Istnieją dowody sugerujące, że rzeczywista granica może wynosić 4/3 (Carr i Vempala, 2004 [Wersja bezpłatna] [Dobra wersja] ).

• Górna granica zbliżalności została ostatnio obniżona do (Mucha 2011 „13/9 - aproksymacja do graficznego TSP” [ PDF ])$13/9$

Daj wyraźną funkcję o wykładniczej złożoności obwodu.

Shannon udowodnił w 1949 r., Że jeśli losowo wybierzesz funkcję boolowską, ma ona wykładniczą złożoność obwodu z prawdopodobieństwem prawie jeden.

Najlepsza dolna granica dla jawnej funkcji boolowskiej którą mamy do tej pory, to K. Iwamy, O. Lachish, H , Morizumi i R. Raz.$f:\{0,1\}^n \to \{0,1\}$$5n - o(n)$

Jaka jest złożoność zapytań polegająca na testowaniu płynności trójkątów w gęstych grafach (tj. Odróżnianie grafów wolnych od trójkątów od tych daleko od braku trójkątów)? Znana górna granica to wieża wykładnicza w , podczas gdy znana dolna granica jest tylko nieznacznie super wielomianowa w . Jest to dość podstawowe pytanie w teorii ekstremalnych grafów / kombinatorykach addytywnych, która jest otwarta od prawie 30 lat.$\epsilon$$1/\epsilon$$1/\epsilon$

Oddziel NEXP od BPP. Ludzie wierzą, że BPP = P, ale nikt nie może oddzielić NEXP od BPP.

Wiem, że OP poprosił o tylko jeden problem na post, ale konferencje RTA (Techniki przepisywania i ich aplikacje) 1 i TLCA (Typed Lambda Calculi i ich aplikacje) przechowują listy otwartych problemów w swoich polach 2 . Listy te są dość przydatne, ponieważ zawierają również wskazówki do wcześniejszych prac wykonanych przy próbie rozwiązania tych problemów.

Derandomizacja problemu testowania tożsamości wielomianowej

Problem jest następujący: Biorąc pod uwagę obwód arytmetyczny obliczający wielomian , czy jest identycznie zerowy?$P$$P$

Problem ten można rozwiązać w losowym czasie wielomianowym, ale nie wiadomo, że można go rozwiązać w deterministycznym czasie wielomianowym.

Powiązane jest Shub and Smale za przypuszczenie. Biorąc pod uwagę wielomian , definiujemy jego -kompleksowość jako rozmiar najmniejszego obwodu arytmetycznego obliczającego stosując jedyną stałą . Dla wielowymiarowego wielomianu , niech będzie jego liczbą rzeczywistych pierwiastków.$\tau$$P$$\tau$$\tau(P)$$P$$1$$P\in\mathbb Z[x]$$z(P)$

Wykazać, że istnieje uniwersalna stała taka, że ​​dla każdego , .$c$$P\in\mathbb Z[x]$$z(P)\le (1+\tau(P))^c$

Czy istnieje twierdzenie Quantum PCP?

Istnieje wiele otwartych problemów w obliczeniach lambda (wpisywanych i bez wpisywania). Szczegółowe informacje można znaleźć na liście otwartych problemów TLCA ; jest też ładna wersja PDF bez ramek.

Szczególnie podoba mi się problem nr 5:

Czy w istnieją terminy, które nie są ale można je pisać za pomocą pozytywnych typów rekurencyjnych?$F_ω$

Czy problem z dyskretnym logarytmem występuje w P?

Niech być cykliczna grupa rzędu oraz w taki sposób, jest generatorem . Problem znalezienia takiego, że jest znany jako dyskretny problem logarytmiczny (DLP). Czy istnieje (klasyczny) algorytm rozwiązywania DLP w najgorszym przypadku czasu wielomianu w liczbie bitów ?$G$$q$$g,h \in G$$g$$G$$n \in \mathbb{N}$$g^n = h$$q$

Istnieją odmiany DLP, które uważa się za łatwiejsze, ale nadal nie zostały rozwiązane. Obliczeniowa problemem Diffie-Hellman (CDH) zwraca się do znalezienia podane a . Decyzyjny problemem Diffie-Hellman (DDH) prosi o decydującym, biorąc pod uwagę , jeśli .$g^{a b}$$g, g^a$$g^b$$g, g^a, g^b, h \in G$$g^{a b} = h$

Najwyraźniej DLP jest trudny, jeśli CDH jest trudny, a CDH jest trudny, jeśli DDH jest trudny, ale nie są znane żadne odwrotne redukcje, z wyjątkiem niektórych grup. Założenie, że DDH jest trudne, jest kluczem do bezpieczeństwa niektórych kryptosystemów, takich jak ElGamal i Cramer-Shoup .

Gry parzystości to gry graficzne dla dwóch graczy o nieskończonym czasie trwania, których naturalnym problemem decyzyjnym jest NP i co-NP, a których naturalnym problemem wyszukiwania jest PPAD i PLS.

http://en.wikipedia.org/wiki/Parity_game

Czy gry parzystości można rozwiązać w czasie wielomianowym?

(Mówiąc bardziej ogólnie, od dawna głównym otwartym pytaniem w programowaniu matematycznym jest to, czy problemy z komplementarnością liniową macierzy P można rozwiązać w czasie wielomianowym?)

Obszar sparametryzowanej złożoności ma wiele otwartych problemów.

Rozważ problemy decyzyjne

• biorąc pod uwagę czy istnieje wykres wierzchołka o rozmiarze dla wykresu ?$(G,k)$$k$$G$
• biorąc pod uwagę czy istnieje zadowalające przypisanie wagi dla wzoru ?$(F,k)$$k$$F$
• biorąc pod uwagę czy na wykresie istnieje klika wielkości ?$(G,k)$$k$$G$
• itp...

Wiele, WIELE, problemów kombinatorycznych istnieje w tej formie. Sparametryzowana złożoność uważa algorytm za „wydajny”, jeśli jego czas działania jest górny ograniczony przez gdzie jest funkcją arbitralną, a jest stałą niezależną od . Dla porównania zauważmy, że wszystkie takie problemy można łatwo rozwiązać w .$f(k)n^c$$f$$c$$k$$n^{O(k)}$

Ramy te modelują przypadki, w których szukamy małej struktury kombinatorycznej, i możemy sobie pozwolić na wykładniczy czas działania w odniesieniu do wielkości rozwiązania / świadka .

Problem z takim algorytmem (np. Przykrycie wierzchołków) nazywa się Fixed Parameter Tractable (FPT).

Sparametryzowana złożoność jest dojrzałą teorią i ma zarówno silne podstawy teoretyczne, jak i apel do praktycznych zastosowań. Problemy decyzyjne interesujące dla takiej teorii tworzą bardzo dobrze zorganizowaną hierarchię klas z naturalnymi pełnymi problemami:

Oczywiście jest to otwarte, jeśli którekolwiek z takich wpisów jest surowe, czy nie. Zauważ, że jeśli to SAT ma algorytm subklonencyjny (to nie jest trywialne). Ostatnie zdanie łączy sparametryzowaną złożoność ze wspomnianym powyżej .E T $FPT=W[1]$$ETH$

Zauważ też, że badanie takich zawaleń nie jest pustym ćwiczeniem: udowodnienie, że jest równoważne, aby udowodnić, że istnieje algorytm możliwy do ustalenia w ustalonych parametrach w celu znalezienia klik.$W[1]=FPT$$k$