Pytania otagowane jako big-list

Pytania, których odpowiedzi to duża lista pozycji (książki, twierdzenia, oprogramowanie, ...)


2
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,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 jest jasne, na podstawie dyskusji na NP-zupełnym wariantu faktoringu. ),N.P.NPNP …

4
Problemy, o których wiadomo, że nie są kompletne z PSPACE
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 i C.”: Złożoność 1x1 Godziny …

6
Algorytmy strumienia danych „Dziel i rządź”
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 itp. Przybliżone tak zwane „oparte na …


4
Lista problemów silnie NP-trudnych z danymi liczbowymi
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, 3-KOLOURABILNOŚĆ. Czy ktoś zna listę problemów o wysokim stopniu NP? Jeśli nie, zbudujmy tutaj. Czy …

3
Dowody znalezione przez komputer
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 komponenty. Celem tego pytania jest wykazanie dowodów, które zostały (całkowicie lub częściowo) znalezione …

2
Eksponaty dla muzeum komputerów
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 tematów związanych z informatyką / informatyką / komunikacją / matematyką. Choć …


2
Problemy bez znanej przewagi kwantowej
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 znanym klasycznym. Mówiąc bardziej wstępnie, sugerowałbym również sortowanie jako kolejny problem, …

4
Algorytmy aproksymacyjne stosowane w algorytmach dokładnych
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ć jakiś problem :B ∘ Ab∘ZAB \circ A Użyj algorytmu aproksymacyjnego rozwiązującego problem …

1
Jakie są główne problemy badawcze w transakcjach rozproszonych?
Tło: Przetwarzanie transakcji jest tradycyjnym tematem badań w teorii baz danych. Obecnie transakcje rozproszone są popularyzowane przez wielkoskalowe rozproszone systemy pamięci masowej, które zazwyczaj obejmują partycjonowanie danych (zwane także shardingiem) i replikację danych . Jakie są główne problemy badawcze w transakcjach rozproszonych? Czy istnieją dobrze znane teorie i rozwiązania, które …

4
Konstrukcje lepsze niż losowe.
Interesują mnie przykłady konstrukcji teorii złożoności, które są lepsze niż konstrukcje losowe. Jedyny znany mi przykład takiej konstrukcji dotyczy kodów korygujących błędy. Kody geometrii algebraicznej są lepsze w niektórych zakresach parametrów niż kody losowe. Można łatwo skonstruować takie sztuczne przykłady. Interesują mnie przykłady takie jak algebraiczne kody geometrii, w których …


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.