Jakie przypuszczenia i główne otwarte problemy są najważniejsze w algorytmicznej teorii gier (lub ogólnie teorii gier w odniesieniu do CS)? Na przykład rozdzielczość NASH jako kompletna z PPAD byłaby, jak sądzę, największa do czasu jej rozwiązania. (Dodano: rozwiązanie stosunku PPAD do P i NP to...
Czy znane są wyniki, które wykluczają istnienie struktur danych „zbyt dobrych, by były prawdziwe”? Na przykład: czy można dodać funkcjonalność SplitSplitSplit i do struktury danych obsługi zamówień (patrz Dietz i Sleator STOC '87 ) i nadal uzyskiwać operacje czasowe...
Rozpoczynam doktorat tej jesieni i planuję pracować nad teorią złożoności. Tworzę listę ważnych prac, które powinien znać każdy teoretyk złożoności. Jakie dokumenty poleciłbyś osobie takiej jak ja? I proszę krótko wyjaśnić, dlaczego uważasz, że ten papier jest...
Spojrzałem w Internecie, ale nie mogłem znaleźć żadnej „dużej listy” wariantów problemu SAT. Oprócz (wspólnego) SAT, k-SAT, MAX-kSAT, Half-SAT, XOR-SAT, NAE-SAT jakie jeszcze są warianty? (również będzie to bardzo przydatne, jeśli podano klasy złożoności (tam, gdzie to...
Szukam przykładów wyników, które są sprzeczne z intuicją ludzi podczas ogólnej dyskusji publiczności. Wyniki, które na pytanie ekspertów niebędących ekspertami „co podpowiada ci intuicja?”, Prawie wszystko byłoby błędne. Oświadczenie o wynikach powinno być łatwe do wyjaśnienia studentom w cs /...
Po dyskusji na temat dolnych granic dla 3SAT [ 1 ] zastanawiam się, jakie są główne wyniki dolnej granicy sformułowane jako kompromisy czasoprzestrzenne. Wykluczam wyniki takie jak, powiedzmy, twierdzenie Savitcha; dobry wpis koncentrowałby się na jednym problemie i jego granicach. Przykładem może...
Teoria kompilatora wydaje się być dość sprawdzonym przedmiotem. Jakie są otwarte problemy lub aktualne badania w tej
Aby uczcić 100. urodziny Alana Turinga, chcę obejrzeć film dokumentalny o jego życiu. Istnieje jednak kilka dokumentów do wyboru. Który dokument o Alanie Turingu jest twoim ulubionym? Podaj tylko jeden dokument na
Czy są jakieś najnowsze książki na temat algorytmów online? Znam tylko dwie książki na ten temat. Obliczenia online i analiza konkurencji Allana Borodina i Ran El-Yaniv: Jest to klasyczna, ale stara książka i nie zawiera wielu najnowszych osiągnięć w tej dziedzinie. Projektowanie konkurencyjnych...
Załóżmy, że spotykasz się z programistami, którzy odbyli profesjonalne kursy programowania (/ self-think), ale nie studiowali matematyki na poziomie uniwersyteckim. Aby pokazać im piękno TCS, chciałbym zebrać kilka fajnych wyników / otwartych pytań pochodzących z TCS, które można łatwo...
Jakie istnieją przydatne algorytmy, które działają na ogromnych strumieniach danych, a także ich wyniki są dość małe i można obliczyć wynik dla mieszanki dwóch strumieni, łącząc w jakiś sposób ich wyniki? Mogę wymienić kilka: Oczywiste rzeczy, takie jak suma, min, maksimum, liczba, najwyższe K...
Jakie są problemy z następującymi właściwościami: 1) są ograniczeniem (prawdopodobnie dobrze znanych) problemów, które są kompletne z PSPACE; 2) wersje ograniczone są w PSPACE, ale jest to otwarty problem, jeśli są one kompletne (lub nawet jeśli są trudne w wersji NP). Cztery przykłady z „puzzli...
Szukam listy o znanej lub nieznanej złożoności różnych problemów teoretycznych / algebraicznych. Na przykład, GCD w jest otwarty,N.do1NC1NC^1 faktoring w jest otwarty,P.PP obliczanie kohomologii snopów to -hard# P#P\#P , Arora i Barak stwierdzają, że wariant faktoringu jest -Complete (choć nie...
Jakie są niektóre (mało znane) twierdzenia, że jeśli prawda, PH musi się załamać? Docenia się odpowiedzi zawierające krótkie stwierdzenie wysokiego poziomu z referencjami. Próbowałem przeszukać wstecz bez większego
Jestem studentką CS. Zrobiliśmy teorię grafów w jednym kursie. Uważam to za interesujące. Jakie są prawdziwe zastosowania teorii grafów w dziedzinie informatyki? Na przykład odkryłem, że niektóre koncepcje teorii grafów można wykorzystać do projektowania sieci. Jakie są inne podobne...
Wydaje mi się, że wszystkie muzea i wystawy związane z komputerami obejmują jedynie historię maszyn komputerowych, ale nic na temat informatyki. Uczestniczysz w tworzeniu nowego Muzeum Informatyki, którego zadaniem jest edukacja, rozrywka i inspirowanie ogółu społeczeństwa w szerokim zakresie...
Algorytmy aproksymacyjne mogą dawać wynik do pewnego stałego współczynnika. Jest to nieco mniej satysfakcjonujące niż dokładne algorytmy. Jednak stałe czynniki są ignorowane w złożoności czasowej. Zastanawiam się więc, czy następująca sztuczka jest możliwa lub została zastosowana, aby rozwiązać...
W 1996 r. Długotrwały otwarty problem został rozwiązany przez komputer; mianowicie, że algebra Robbinsa i algebra Boole'a są takie same. Dowód został znaleziony przez automatyczną powiedzonkę twierdzeń. Ponadto znany dowód twierdzenia o czterech kolorach zawiera generowane komputerowo...
Szukam silnie trudnych NP problemów dla redukcji. Do tej pory znalazłem następujące problemy: Problem z 3 partycjami problem z pakowaniem pojemników Trójwymiarowe dopasowanie numeryczne TSP Każdy problem NP-zupełny bez danych liczbowych, np. SATYSFIABILNOŚĆ, CYKL HAMILTONII,...
Zastanawiałem się, jaka jest lista obecnych naturalnych problemów obliczeniowych, dla których nie ma znanej przewagi złożoności przy użyciu komputera kwantowego. Na początek, myślę, że obliczenie odległości edycji jest tym, dla którego najszybszy znany algorytm kwantowy wydaje się być najszybszym...