Teoretyczne informatyka

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

1
Szybkie mieszanie łańcuchów Markowa na 3-kolorowych cyklach
Dynamika Glaubera to łańcuch Markowa na kolorach wykresu, w którym na każdym kroku próbuje się pokolorować losowo wybrany wierzchołek o losowym kolorze. Nie miesza się w przypadku 3 kolorów w 5 cyklach: istnieje 30 3 kolorów, ale tylko 15 z nich można osiągnąć za pomocą etapów kolorowania pojedynczego wierzchołka. Mówiąc …
2
MIP z wydajnymi dowodami
Powszechnie wiadomo, że zestawem języków posiadających dwuczłonowy interaktywny system proof, w którym weryfikator działa w czasie wielomianowym (MIP), jest NEXP. Ale czy znane są granice mocy takich interaktywnych dowodów, gdy dowody mają ograniczoną moc? Na przykład, jaka jest klasa języków, które dopuszczają dowody interaktywne z dwoma dowodami z dowodami czasu …
3
Czytnik, pisarz monady
Niech będzie CCC . Niech być bifunctor produkt na . Ponieważ Cat to CCC, możemy curry :( × ) C ( × )CCC(×)(×)(\times)CCC(×)(×)(\times) curry(×):C→(C⇒C)curry(×):C→(C⇒C)curry (\times) : C \rightarrow(C \Rightarrow C) curry(×)A=λB.A×Bcurry(×)A=λB.A×Bcurry (\times) A = \lambda B. A \times B Kategoria funktora ma zwykłą strukturę monoidalną. C⇒CC⇒CC \Rightarrow C Monoid w …
4
Alternatywne pojęcie złożoności oparte na luce między brutalną siłą a najlepszym algorytmem?
Zwykle wydajne algorytmy mają wielomianowe środowisko wykonawcze i wykładniczo dużą przestrzeń rozwiązania. Oznacza to, że problem musi być łatwy w dwóch aspektach: po pierwsze, problem można rozwiązać w wielomianowej liczbie kroków, a po drugie, przestrzeń rozwiązania musi być bardzo ustrukturyzowana, ponieważ środowisko wykonawcze jest tylko polilogarytmiczne pod względem liczby możliwych …
2
Problem cięcia bez H
Załóżmy, że otrzymałeś połączony, prosty, niekierowany wykres H. Problem cięcia bez H jest zdefiniowany następująco: Biorąc pod uwagę prosty, nieukierowany wykres G, istnieje cięcie (podział wierzchołków na dwa niepuste zbiory, L, R), tak że oba wykresy indukowane przez zestawy cięcia (L i R) nie zawierają izomorficznego subgrafu do H . …
1
Czy istnieje związek między relacyjną algebrą / rachunkiem a teorią kategorii?
Mam świadomość co najmniej dwóch różnych teoretycznych podejść do zrozumienia relacyjnych baz danych: relacyjnej algebry / rachunku Codda i teorii kategorii. Czy istnieje związek między tymi dwoma podejściami? Czy są w pewnym sensie równoważne? Czy są jakieś prace wprowadzające wyjaśniające, w jaki sposób oba te środowiska wyjaśniają relacyjne bazy danych? …
2
Status quo teorii kategorii i monad w teoretycznych badaniach informatycznych?
Tło . Jestem studentem studiów licencjackich, który interesuje się badaniami związanymi z teorią kategorii, monadami i Haskellem, i chcę znaleźć temat do mojej pracy licencjackiej w tej dziedzinie. Spojrzałem na gazetę Eugenio Moggi , „ Pojęcia obliczeń i monad ”, 1991, i jeszcze niewiele z tego rozumiem. Prawdopodobnie będę potrzebować …
1
Funkcje boolowskie, w których czułość jest równa czułości bloku
Część pracy nad czułością w porównaniu do czułości bloku miała na celu zbadanie funkcji z możliwie największą luką między s(f)s(f)s(f) i bs(f)bs(f)bs(f) w celu rozstrzygnięcia przypuszczenia, że bs(f)bs(f)bs(f) jest tylko wielomianowo większy niż s(f)s(f)s(f) . Co z przeciwnym kierunkiem? Co wiadomo o funkcjach, w których s(f)=bs(f)s(f)=bs(f)s(f) = bs(f) ? Trywialnie, …
1
Wykonalność maszyn Gödel
Ostatnio natknąłem się na dość interesującą konstrukcję teoretyczną. Tak zwana maszyna Gödela To ogólne narzędzie do rozwiązywania problemów, które jest zdolne do samooptymalizacji. Nadaje się do środowisk reaktywnych. Jak rozumiem, można go zaimplementować jako program do uniwersalnej maszyny Turinga, choć jego wymagania wykraczają daleko poza obecnie dostępny sprzęt. Nie mogłem …
1
Zabronione osoby niepełnoletnie w przypadku związanych z nimi wykresów rodzajów
Powszechnie wiadomo, że i K 3 , 3 są niedozwolone w przypadku wykresów planarnych. Istnieją setki zakazanych nieletnich dla wykresów osadzanych na torusie. Liczba niedozwolonych nieletnich dla wykresów osadzanych na powierzchni rodzaju g jest funkcją wykładniczą g . Moje pytanie brzmi:K5K5K_5K3,3K3,3K_{3,3} Ma wyraźnego wykresem o t wierzchołków (co nie jest …
3
Edytuj odległość między dwiema partycjami
Mam dwie partycje [1…n][1…n][1 \ldots n] i szukam odległości edycji między nimi. W ten sposób chcę znaleźć minimalną liczbę pojedynczych przejść węzła do innej grupy, które są niezbędne do przejścia z partycji A na partycję B. Na przykład odległość od {0 1} {2 3} {4}do {0} {1} {2 3 4}wynosi …
2
Czy
W „ostatnim akapicie” „pierwszej strony” następującego artykułu: Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , „Jeśli NP ma obwody wielomianowe, wówczas MA = AM”, Theoretical Computer Science, 1995. Napotkałem nieco sprzeczne z intuicją twierdzenie: (ΣP2∩ΠP2)NP=ΣP3∩ΠP3(Σ2P∩Π2P)NP=Σ3P∩Π3P(\Sigma^P_2 \cap \Pi^P_2)^{NP} = \Sigma^P_3 \cap \Pi^P_3 Myślę, że powyższa tożsamość została …
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.