Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

2
Czy istnieje bezpośrednia / naturalna redukcja, aby liczyć niedwustronne idealne dopasowania za pomocą stałego?
Zliczanie liczby idealnych dopasowań na wykresie dwustronnym można natychmiast zredukować do obliczenia wartości stałej. Ponieważ znalezienie idealnego dopasowania na grafie dwustronnym występuje w NP, istnieje pewna redukcja z grafów dwustronnych do stałych, ale może to wiązać się z nieprzyjemnym wielomianowym powiększeniem poprzez zastosowanie redukcji Cooka do SAT, a następnie twierdzenia …
3
Twardość aproksymacji - błąd addytywny
Istnieje bogata literatura i co najmniej jedna bardzo dobra książka określająca znaną twardość wyników przybliżenia dla problemów trudnych dla NP w kontekście błędu multiplikatywnego (np. 2-przybliżenie dla pokrywy wierzchołków jest optymalne przy założeniu UGC). Obejmuje to również dobrze zrozumiałe klasy złożoności aproksymacji, takie jak APX, PTAS i tak dalej. Co …
3
Czy Magic: the Gathering Turing jest ukończony?
Zdaję sobie sprawę z bardzo konkretnego pytania i wątpię, że odpowie na nie każdy, kto nie jest zaznajomiony z zasadami Magii. Przeniesiony do Draw3Cards . Oto kompleksowe zasady gry Magic: the Gathering . Zobacz to pytanie, aby uzyskać listę wszystkich magicznych kart. Moje pytanie brzmi - czy gra Turing jest …
1
Złożoność przestrzenna algorytmu Coppersmitha – Winograda
Algorytm Coppersmitha – Winograda jest asymptotycznie najszybszym znanym algorytmem do mnożenia dwóch macierzy kwadratowych. Czas działania ich algorytmu to który jest najlepiej znany do tej pory. Jaka jest złożoność przestrzeni tego algorytmu? Czy to jest w ?n×nn×nn \times nO(n2.376)O(n2.376)O(n^{2.376})Θ(n2)Θ(n2)\Theta(n^2)
3
Czy możemy kwantyfikować „stopień kwantowości” w algorytmie kwantowym?
Splątanie jest często utrzymywane jako kluczowy składnik, który sprawia, że ​​algorytmy kwantowe są dobrze ... kwantowe, i można to prześledzić do stanów Bella, które niszczą ideę fizyki kwantowej jako modelu probabilistycznego w stanie ukrytym. W teorii informacji kwantowej (z mojego raczej słabego zrozumienia) splątanie może być również wykorzystane jako konkretny …
2
Hamiltoniczność wykresów k-regularnych
Wiadomo, że NP-kompletne jest sprawdzenie, czy cykl hamiltonowski istnieje na 3-regularnym wykresie, nawet jeśli jest on płaski (Garey, Johnson i Tarjan, SIAM J. Comput. 1976) lub dwustronny (Akiyama, Nishizeki, i Saito, J. Inform. Proc. 1980) lub w celu przetestowania, czy cykl hamiltonowski istnieje na wykresie 4-regularnym, nawet jeśli jest to …
8
Obliczanie odległości Levenshteina szybko
Biorąc pod uwagę ogromną bazę dozwolonych słów (posortowane alfabetycznie) i słowo, znajdź słowo z bazy danych, która jest najbliższa podanemu słowu pod względem odległości Levenshteina. Naiwnym podejściem jest oczywiście po prostu obliczenie odległości levenshteina między danym słowem a wszystkimi słowami w słowniku (możemy przeprowadzić wyszukiwanie binarne w bazie danych przed …
6
Czy występują problemy NP-zupełne z rozwiązaniami wielomianowego oczekiwanego czasu?
Czy są jakieś problemy z NP-zupełnością, dla których znany jest algorytm, że oczekiwany czas działania jest wielomianowy (dla pewnego rozsądnego rozkładu między instancjami)? Jeśli nie, to czy istnieją problemy, dla których ustalono istnienie takiego algorytmu? Czy istnienie takiego algorytmu sugeruje istnienie deterministycznego wielomianowego algorytmu czasu?
2
Jeśli techniki uczenia maszynowego będą się ciągle poprawiać, jaka jest rola algorytmiki w przyszłości?
Spójrzmy w przyszłość za 30 lat. Bądźmy optymistami i załóżmy, że obszary związane z uczeniem maszynowym rozwijają się tak szybko, jak to, co widzieliśmy w ciągu ostatnich 10 lat. Byłoby świetnie, ale jaka byłaby rola tradycyjnej algorytmiki w takiej przyszłości? Tutaj przez „tradycyjną algorytmię” odnoszę się do zwykłego procesu, który …
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.