Problemy, o których wiadomo, że są otwarte w literaturze, i każdy problem, który po postawieniu decyduje się być otwarty przez społeczność.
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: Tylko jeden problem na odpowiedź Podaj krótki opis i wszelkie odpowiednie linki...
Losowanie dwóch ciągów znaków polega na przeplataniu znaków w nowy ciąg znaków, utrzymując porządek znaków każdego łańcucha. Na przykład, MISSISSIPPIjest losowanie MISIPPi SSISI. Nazwijmy kwadrat ciągów, jeśli jest to tasowanie dwóch identycznych ciągów. Na przykład ABCABDCDjest kwadratowy,...
tło Kilka lat temu, kiedy byłem studentem, otrzymaliśmy zadanie domowe z analizy zamortyzowanej. Nie udało mi się rozwiązać jednego z problemów. Poprosiłem o to w teorii porównawczej , ale nie uzyskałem zadowalającego rezultatu. Pamiętam kurs, który TA nalegał na coś, czego nie mógł udowodnić, i...
Po przestudiowaniu deterministycznych automatów skończonych (DFA) w undergrad poczułem, że są one bardzo dobrze rozumiane. Moje pytanie brzmi, czy jest coś, czego wciąż nie rozumiemy. Nie mam na myśli uogólnień DFA, ale oryginalne niezmodyfikowane DFA, które badamy w studiach licencjackich. To...
W wątku Główne nierozwiązane problemy w informatyce teoretycznej? Iddo Tzameret napisał następujący doskonały komentarz: Myślę, że powinniśmy rozróżnić między głównymi otwartymi problemami, które są postrzegane jako podstawowe problemy, takie jak P≠NPP≠NP P\neq NP , i głównymi otwartymi...
Rozważ rozłącznych rodzin podzbiorów {1,2,…, n}, F 1 , F 2 , … F t .tttfa1, F.2), … FtF1,F2,…Ft{\cal F}_1,{\cal F_2},\dots {\cal F_t} Przypuszczam, że (*) Dla każdego i każdy R ∈ F ı i T ∈ K K , jest S ∈ F j , który zawiera R ∩ T .i < j < ki<j<ki \lt j \lt kR ∈ FjaR∈FiR \in {\cal...
Aktualizacja : Zestaw przeszkód (tj. „Bariera” NxM pomiędzy rozmiarami siatki do barwienia i bezbarwności) dla wszystkich 4-kolorów bez monochromatycznych prostokątów jest teraz znany . Czy ktoś ma ochotę wypróbować 5 kolorów? ;) Z teorii Ramseya wynika następujące pytanie . Rozważmy -coloring...
Ten problem jest inspirowany pytaniem MO , które moim zdaniem było bardzo interesujące. Jaki jest najstarszy otwarty problem w TCS? To pytanie wymaga wyjaśnienia. Po pierwsze, czym jest TCS? Myślę, że istnienie liczb nieparzystych idealnych nie jest TCS. Powiedziałbym, że dziesiątym...
Ostatnio Gil Kalai i Dick Lipton napisali fajny artykuł na temat ciekawej hipotezy zaproponowanej przez Petera Sarnaka, eksperta w dziedzinie teorii liczb i hipotezy Riemanna. Przypuszczenie. Niech będzie funkcją Möbiusa . Załóżmy, że f : N → { - 1 , 1 } jest funkcją A C 0 z wejściem k w postaci...
Problem polega na obliczeniu wielomianu . Załóżmy, że wszystkie współczynniki mieszczą się w słowie maszynowym, tzn. Można nimi manipulować w czasie jednostkowym.(a1x+b1)×⋯×(anx+bn)(a1x+b1)×⋯×(anx+bn)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Możesz zrobić czas , stosując FFT w sposób...
W duchu takich ogólnych dyskusji, jak ta , otwieram ten wątek z zamiarem zebrania opinii na temat otwartych wyzwań i gorących tematów w badaniach nad językami programowania . Mam nadzieję, że dyskusja może nawet ujawnić opinie na temat przyszłości badań w językach programowania. Wierzę, że ten...
Chciałbym zapytać o szczególny przypadek pytania „ Decyzja, czy dany obwód NC 0 oblicza permutację ” QiCheng, na który nie udzielono odpowiedzi. Obwód boolowski nazywa się obwodem NC 0 k , jeżeli każda bramka wyjściowa syntaktycznie zależy od co najwyżej k bramek wejściowych. (Mówimy, że bramka...
Czy następujący problem jest trudny NP? Biorąc pod uwagę konfigurację forum dla międzynarodowych projektów , znajdź jeden legalny ruch.n×nn×nn\times n Odpowiedni problem dla amerykańskich warcabów (inaczej angielskich wersji roboczych) można w prosty sposób rozwiązać w czasie wielomianowym....
Jest deterministycznym algorytmem czasu wielomianowego znanym z następującego problemu: Dane wejściowe: liczba naturalna (w kodowaniu binarnym)nnn Wyjście: liczba pierwsza .p > np>np > n (Według listy otwartych problemów Leonarda Adlemana problem był otwarty w 1995 r.)...
Ranga znaku macierzy A z wpisami + 1, -1 jest najmniejszą rangą (ponad rzeczywistymi) macierzy B, która ma taki sam wzór znaków jak A (tj. dla wszystkich i , j ). Pojęcie to jest ważne w złożoności komunikacji i teorii uczenia się.AijBij>0AijBij>0A_{ij}B_{ij}>0i,ji,ji,j Moje pytanie brzmi:...
Dla stałej można określić w czasie liniowym, biorąc pod uwagę wykres wejściowy G , czy jego szerokość wynosi ≤ k . Jednakże, gdy zarówno k jak i G są podane jako dane wejściowe, problem jest trudny NP. ( Źródło ).k∈Nk∈Nk \in \mathbb{N}GGG≤k≤k\leq kkkkGGG Jednak gdy wykres wejściowy jest płaski ,...
W 1999 r. Petra Schuurman i Gerhard J. Woeginger opublikowali artykuł „Wielomianowe algorytmy aproksymacji czasu dla szeregowania maszynowego: dziesięć otwartych problemów” . Od tego czasu, o ile mi wiadomo, nie pojawiły się recenzje, które dotyczyłyby tej samej listy problemów. Byłoby więc...
Załóżmy, że podano kilka rozłącznych wielokąt prosty w samolocie, a dwa punkty i t zewnątrz każdego wielokąta. Problem najkrótszej ścieżki euklidesowej polega na obliczeniu najkrótszej ścieżki euklidesowej od s do t , która nie przecina wnętrza żadnego wielokąta. Dla konkretności załóżmy, że...
Oprócz (deterministycznej) złożoności komunikacji cc(R)cc(R)cc(R) relacji RRR , inną podstawową miarą ilości potrzebnej komunikacji jest numer podziału protokołu pp(R)pp(R)pp(R) . Zależność między tymi dwoma miarami jest znana aż do stałego współczynnika. Monografia Kushilevitza i Nisana (1997)...
W artykule „A Compendium of Problems Complete for P” autorstwa Greenlawa, Hoovera i Ruzzo (PS) (PDF) znajduje się lista problemów w P, które nie są znane w NC i nie są znane jako P-complete . (Ta lista obejmuje wszystkie otwarte problemy w doskonałej ankiecie przeprowadzonej przez Karpa i...