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 być: „Niech T i S będą czasem działania …
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 …
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 …
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 …
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 szczęścia.
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 …
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 …
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ć …
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 aplikacje?
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, …
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 …
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 …
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 …
Jestem teoretykiem homotopii, interesuje się informatyką. Chciałbym zapytać, jakie są interesujące zastosowania algebry homotopicznej (kategorie modelowe, kategorie nieskończoności, kategorie uproszczone itp.) W informatyce teoretycznej?
Niech będzie alfabetem, czyli niepustym zbiorem skończonym. Łańcuch to dowolna skończona sekwencja elementów (znaków) z . Na przykład to alfabet binarny, a to ciąg znaków dla tego alfabetu.ΣΣ\SigmaΣΣ\Sigma{ 0 , 1 }{0,1} \{0, 1\}011001100110 Zazwyczaj, dopóki zawiera więcej niż 1 element, dokładna liczba elementów w nie ma znaczenia: w najlepszym …
Używamy plików cookie i innych technologii śledzenia w celu poprawy komfortu przeglądania naszej witryny, aby wyświetlać spersonalizowane treści i ukierunkowane reklamy, analizować ruch w naszej witrynie, i zrozumieć, skąd pochodzą nasi goście.
Kontynuując, wyrażasz zgodę na korzystanie z plików cookie i innych technologii śledzenia oraz potwierdzasz, że masz co najmniej 16 lat lub zgodę rodzica lub opiekuna.