Teoretyczne informatyka

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

2
Czy dobre PCP dla NP dają nam dobre PCP dla całej hierarchii wielomianowej?
Twierdzenie PCP stwierdza, że ​​każdy problem decyzyjny w NP ma probabilistycznie sprawdzalne dowody (lub równoważnie, że istnieje kompletny i quasi-dźwiękowy system dla twierdzeń w NP wykorzystujący stałą złożoność zapytań i logarytmicznie wiele losowych bitów). „Mądrość ludowa” otaczająca twierdzenie PCP (ignorując przez chwilę znaczenie PCP dla teorii przybliżenia) polega na tym, …
2
Algorytm wyliczania kliki
Czytam stary artykuł MC Golumbica na temat wykresów EPT (przecięcie krawędzi ścieżek na drzewie). W artykule pokazano, że liczba maksymalnych klików wystąpienia wykresu EPT jest wielomianowa. Stwierdza, że ​​jeśli wyrocznia zgłasza, że ​​wykressolsolG jest wykresem EPT, możliwe jest znalezienie maksymalnej kliki za pomocą standardowego algorytmu wyliczania kliki. Po pierwsze, jakie …
2
Badanie wnioskowania na podstawie typu strony wywołującej?
Próbuję dowiedzieć się więcej na temat sprawdzania typu całego programu i systemów wnioskowania o typie, które wykorzystują informacje z witryn wywołań funkcji do obliczania informacji o typie (oprócz standardowego podejścia do używania treści funkcji). Na przykład taki algorytm może użyć wywołania funkcji, na przykład, foo(1)aby wnioskować, że funkcja w foopobiera …
1
Rozkład funkcji podmodularnej
Biorąc podmodular funkcji faff na Ω =X1∪X2)Ω=X1∪X2\Omega=X_1\cup X_2 gdzie X1X1X_1 i X2)X2X_2 są rozłączni i fa( S) =fa1( S∩X1) +fa2)( S∩X2))f(S)=f1(S∩X1)+f2(S∩X2)f(S)=f_1(S\cap X_1)+f_2(S\cap X_2). Tutajfa1f1f_1 i fa2)f2f_2 są podmodularne X1X1X_1 i X2)X2X_2 odpowiednio. Tutaj X1,X2),fa1,fa2)X1,X2,f1,f2X_1,X_2,f_1,f_2 są nieznane i dostęp tylko do zapytania o wartość faffjest podawany. Czy istnieje algorytm politime, który …
3
Pośrednie przykłady z formalnej teorii języka
Uczę się algebraicznej teorii parsowania. Moim pierwszym problemem jest zidentyfikowanie przykładów semieralnych, które są specyficzne dla formalnej teorii języka. Oto próba skonstruowania dwóch przykładów. 1 Biorąc pod uwagę gramatykę CNF, elementy semeryzacji są zestawami symboli terminalnych i nieterminalnych z operacjami: i) Mnożenie , łączenie dwóch zestawów parami zgodnie z regułą …
1
Czy Max-Cut APX-complete na grafach bez trójkątów?
W problemie Max-Cut szuka się podzbioru S wierzchołków danego prostego niekierowanego wykresu, tak że liczba krawędzi między S a dopełnieniem S jest tak duża, jak to możliwe. Max-Cut jest kompletny APX na wykresach ograniczonego stopnia [PY91], i faktycznie APX-kompletny na wykresach sześciennych (tj. Grafach stopnia 3) [AK00]. Max-Cut jest NP-kompletny …
1
Wyrażenia regularne bez zmian
Zastanawiałem się, jakie zestawy języków są generowane przez ograniczenia wyrażeń regularnych. Załóżmy, że wszystkie ograniczenia mają stały symbol dla każdego elementuΣΣ\Sigmai konkatenacja. Następnie można utworzyć osiem klas poprzez obecność lub brak dopełniacza / negacji, zmiany / unii i gwiazdy Kleene. (Tak, „normalne” wyrażenia regularne nie majądoC^C operator, ale tutaj jest …
3
Pytanie techniczne dotyczące losowych spacerów
(Na moje pierwotne pytanie wciąż nie ma odpowiedzi. Dodałem dalsze wyjaśnienia.) Analizując losowe spacery (na niekierowanych grafach), widząc losowy spacer jako łańcuch Markowa, wymagamy, aby wykres nie był dwustronny, aby obowiązywało podstawowe twierdzenie o łańcuchach Markowa. Co się stanie, jeśli wykres GGGjest zamiast tego dwustronny? Jestem szczególnie zainteresowany czasem uderzeniahi,jhi,jh_{i,j}, …
3
Znajdowanie wszystkich cykli
Mam skończony zestaw S.SS, funkcja fa: S→ Sf:S→Sf:S\to Soraz całkowite zamówienie &lt;&lt;< na S.SS. Chcę znaleźć liczbę różnych cykliS.SS. Dla danego elementu s ∈ Ss∈Ss\in S Mogę użyć algorytmu Floyda (lub Brenta itp.), Aby znaleźć długość cyklu, w którym powtarzały się aplikacje faff wysyła sssdo; przy odrobinie wysiłku mogę zidentyfikować …
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.