Pytania otagowane jako open-problem

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ść.

11
Jak trudne jest tasowanie sznurka?
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, ponieważ jest to przetasowanie ABCDi ABCD, ale ciąg ABCDDCBAnie jest kwadratowy. Czy istnieje …
10
Czy pozostały jakieś otwarte problemy związane z DFA?
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 jest niejasne pytanie, ale mam nadzieję, że masz pomysł. …
10
Jeden stos, dwie kolejki
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 powiedział, że zapomniał dowodu i …
13
Otwarte problemy na granicach TCS
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 problemami, które będą stanowić przełom techniczny, jeśli zostaną rozwiązane, ale niekoniecznie tak fundamentalne, …
6
Siatka
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 z n -by- m wykres siatki. Występuje, gdy cztery …
7
Jaki jest najstarszy otwarty problem w TCS?
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 problemem Hilberta jest TCS. Myślę, że problemy takie jak …
1
Mnożenie n wielomianów stopnia 1
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 drzewny. Czy możesz zrobić O ( n log n ) …
2
Decyzja, czy NC
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 wyjściowa g syntaktycznie zależy …
3
Czy NP jest trudny do prawidłowego grania w drafty międzynarodowe?
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. Istnieją trzy główne różnice między tymi dwiema grami.n×nn×nn\times n Pierwszą i najbardziej znaczącą …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.