Teoretyczne informatyka

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

2
Czy niedeterministyczne automaty do chodzenia po drzewie są silniejsze niż te deterministyczne?
Aktualizacja: Wygląda na to, że ten problem został niedawno zbadany i rozwiązany, zobacz ten artykuł wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton A także tę ankietę: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf Załóżmy, że zamiast zwykłego zestawu słów {0,1} *, nasze słowa nie są liniowe, ale raczej podane na jakiejś strukturze drzewa. Aby zapobiec „zagubieniu się” naszych maszyn, zdefiniuj …
3
Trudność ze znalezieniem co najwyżej słowa
Opis problemu: Pozwolić MMM być (potencjalnie niedeterministycznym) automatem wypychającym i pozwól AA\cal Abyć jego alfabetem wejściowym. Czy jest jakieś słowo?w∈A∗w∈A∗w \in \cal A^* św |w|≤k|w|≤k|w| \leq k które jest akceptowane przez MMM ? Czy ten problem NP-jest kompletny? Czy zostało to zbadane? Czy istnieje algorytm pozwalający znaleźć takie słowo?
1
Źródło modułowego wykresu rozkładu
Podczas wprowadzania modularnego rozkładu grafów większość autorów używa wykresu 11-wierzchołkowego, który kopiuję z wikipedii. Pytanie brzmi, kto jest (są) jego oryginalnymi projektantami. (Nie pytam, kto narysował ten wykres dla wikipedii, ale oryginalne źródło.) Strona wikipedia została utworzona w grudniu 2006 r. Najwcześniejsze źródło, jakie mogę znaleźć, to teza habilitacyjna Christophe …
1
Dowód problemu dla górnej granicy sumy pierwiastków kwadratowych
W [1] Garey i in. określić, co później będzie znane jako problem sumy pierwiastków kwadratowych w trakcie opracowywania kompletności NP euklidesowej TSP. Podane liczby całkowite a1,a2,…,ana1,a2,…,ana_1, a_2, \ldots, a_n i LLLokreśl, czy a1−−√+a2−−√+⋯+an−−√&lt;La1+a2+⋯+an&lt;L\sqrt{a_1} + \sqrt{a_2} + \cdots + \sqrt{a_n} < L Zauważają, że nie jest nawet oczywiste, że problem ten …
2
Jak długo trwa znalezienie krótkiego cyklu na losowym wykresie?
Pozwolić G∼G(n,n−1/2)G∼G(n,n−1/2)G \sim G(n, n^{-1/2}) być losowym wykresem na ≈n3/2≈n3/2\approx n^{3/2}krawędzie Z bardzo dużym prawdopodobieństwemGGG ma wiele 444motocykle. Naszym celem jest wyprodukowanie dowolnego z nich444- motocykle tak szybko, jak to możliwe. Załóżmy, że mamy dostęp do GGG w formie listy sąsiedztwa możemy odnieść sukces ze stałym prawdopodobieństwem w O(n−−√)O(n)O(\sqrt{n}) czas …
1
Ukryte stałe w złożoności algorytmów
W przypadku wielu problemów algorytm o największej złożoności asymptotycznej ma bardzo duży stały współczynnik, który jest ukryty przez dużą notację O. Dzieje się tak w przypadku mnożenia macierzy, mnożenia liczb całkowitych (w szczególności najnowszego algorytmu mnożenia liczb całkowitych O (n log n) Harveya i van der Hoevena), sieci sortowania o …
1
Jakie jest odniesienie do pierwszego twierdzenia Gödela o niekompletności opartego na nierozstrzygalności problemu zatrzymania?
Słabsza forma pierwszego twierdzenia Gödela o niekompletności, którego bezpośrednie dowody są w sposób Gödela długotrwałe, zaangażowane, aw niektórych miejscach raczej sprzeczne z intuicją, ma prosty i intuicyjny dowód oparty na nierozstrzygalności problemu zatrzymania - patrz na przykład https: / /en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof Kto pierwszy zaproponował ten dowód iw jakim artykule lub książce …
4
Wyniki ładowania początkowego, które naprawdę się ładują
Istnieje rodzaj wyników w TCS, zwykle nazywany wynikami ładowania początkowego . Ogólnie rzecz biorąc, ma formę Jeśli twierdzenie zachowuje, to twierdzenie zachowuje.ZAZAAA′ZA′A' gdzie AZAAa to zdania, które wyglądają podobnie, a wydaje się „słabsze” niż , dlatego nazywamy ten typ wyników. Podam kilka konkretnych przykładów:A′ZA′A'AZAAA′ZA′A' Twierdzenie. [Chen and Tell, STOC'19] Napraw …
1
Czy istnieje metoda udowodnienia nieregularności transformacji łańcucha?
Istnieje wiele różnych modeli definiowania transformacji między językami. Przetworniki stanu skończonego i transformacje grafu definiowane przez MSO na grafach łańcuchowych to dwa, z którymi najlepiej się znam. Wiemy, że dwudrożne przetworniki stanu skończonego (które są bardziej ekspresyjne niż ich jednokierunkowe odpowiedniki) i transformacje ciągów definiowane przez MSO przechwytują ten sam …
1
Czy istnieje algorytm, który wyszukuje zakazanych nieletnich?
Twierdzenie Robertsona-Seymour'a głosi, że każda niewielka, zamknięta rodzinasolG\mathcal G wykresów można scharakteryzować przez skończoną liczbę zakazanych nieletnich. Czy istnieje algorytm wejściowy solG\mathcal G wypuszcza zakazanych nieletnich, czy jest to nierozstrzygalne? Oczywiście odpowiedź może zależeć od tego, w jaki sposób solG\mathcal Gjest opisany na wejściu. Na przykład jeślisolG\mathcal G jest podany …
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.