Teoretyczne informatyka

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

1
Czy potrafimy rozróżnić metody ściśle składniowe i semantyczne w języku programowania?
Chociaż dyskusje dowodzą silnych dowodów na normalizację, komentarz ten kontrastuje „model form normalnych” z „metodami czysto składniowymi”. To sprowadza mnie z powrotem do bardziej podstawowego pytania: czy nadal możemy dokładnie rozróżniać konstrukcje składniowe i semantyczne w obliczu modeli opartych na składni? Co z modelami terminów dla algeb, modelami Henkina dla …
1
Czy najdłuższy problem szlaku jest łatwiejszy niż problem najdłuższej ścieżki?
Najdłuższy problem ze ścieżką to trudność NP. (Typowy?) Dowód polega na zmniejszeniu problemu ścieżki hamiltonowskiej (która jest NP-zupełna). Zauważ, że tutaj ścieżka jest uważana za (węzłową) prostą. Oznacza to, że żaden wierzchołek nie może wystąpić więcej niż jeden raz na ścieżce. Oczywiście jest to również proste dla krawędzi (żadna krawędź …
2
Sortowanie przy użyciu stosów tylko do odczytu
Rozważ następujące ustawienie: daje nam stos , który zawiera n elementów.sssnnn możemy użyć stałej liczby dodatkowych stosów .O(1)O(1)O(1) na tych stosach możemy zastosować następujące operacje: sprawdź, czy stos jest pusty, porównaj najlepsze przedmioty z dwóch stosów, usuń najwyższy element ze stosu, wydrukuj najwyższy element na stosie, skopiuj górny element stosu …
2
Teoretyczne gwarancje dla czasów działania metod propagowania przekonań?
Wykazano, że propagacja przekonań jest bardzo skuteczną metodą dzięki badaniom w probabilistycznych modelach graficznych. Jednak nie wiem nic o BP, które byłoby porównywalne z metodami MCMC, w których możemy mieć w pełni wielomianowe losowe schematy aproksymacji (FPRAS) dla problemów z # P-zupełnością. Czy ktoś mógłby wskazać mi jakieś odniesienia?
5
Dokładne algorytmy dla zestawu R-Dominującego na wykresach ograniczonej Treewidth
Biorąc pod uwagę wykres, G=(V,E)G=(V,E)G = (V, E) , to znaleźć optymalną rrr -domination dla GGG . Oznacza to, że chce podzbiór SSS o VVV tak, że wszystkie wierzchołki GGG znajdują się w odległości co najwyżej rrr z pewnym wierzchołka w SSS , przy jednoczesnym zminimalizowaniu rozmiaru .SSS Z tego, …
4
Czy eta-równoważność funkcji jest zgodna z sekwencją Haskella?
Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B. Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda. Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań: seq :: a -> b …
6
Geometryczna interpretacja obliczeń
Będąc fizyką, zostałem przeszkolony, aby patrzeć na wiele problemów z geometrycznego punktu widzenia. Na przykład geometria różniczkowa rozmaitości w układach dynamicznych itp. Kiedy czytam podstawy informatyki, zawsze staram się znaleźć interpretacje geometryczne. Jak wiarygodna geometryczna interpretacja zbiorów rekurencyjnie wyliczalnych (pracowałem nad częścią, w której próbowałem połączyć je z geometrią algebraiczną, …
6
odmiany SAT
Spojrzałem w Internecie, ale nie mogłem znaleźć żadnej „dużej listy” wariantów problemu SAT. Oprócz (wspólnego) SAT, k-SAT, MAX-kSAT, Half-SAT, XOR-SAT, NAE-SAT jakie jeszcze są warianty? (również będzie to bardzo przydatne, jeśli podano klasy złożoności (tam, gdzie to możliwe))
1
Beigel-Tarui transformacja układów ACC
Czytam dodatek na temat dolnych granic ACC dla NEXP w książce Arora i Barak's Computational Complexity . http://www.cs.princeton.edu/theory/uploads/Compbook/accupt.pdf Jednym z kluczowych lematów jest transformacja z obwodów w wielomianowe wielomianowe nad liczbami całkowitymi o stopniu polilogarytmicznym i quasipolynomialnym współczynnikami lub równoważnie , klasa obwodów S Y M + , która jest …
1
Jaka jest minimalna wymagana głębokość redukcji dla NP-twardości SAT?
Jak każdy wie, SAT jest kompletna dla wrt wielomian czasie wiele-jeden redukcje. Nadal jest kompletny z redukcjami wielokrotności A C 0 .NPNP\mathsf{NP}AC0AC0\mathsf{AC^0} Moje pytania brzmi: jaka jest minimalna wymagana głębokość redukcji? Bardziej formalnie, Co najmniej takie, że SAT jest redukcją N P- twardą wr A C 0 d wielokrotności jeden?reddN …
2
Testowanie pozytywności zamiast równości
Alice i Bob mają n-bitowe ciągi i chcą dowiedzieć się, czy są równe, podczas niewielkiej komunikacji. Standardowe rozwiązanie randomizowane polega na traktowaniu ciągów n-bitowych jako wielomianów stopnia a następnie ocenie wielomianów na kilku losowo wybranych elementach z pola o wielkości większej niż n . Wymaga to komunikacji O ( log …
2
Czy Parity-P jest zawarty w PP?
To pytanie zadał Jan Pax na liście mailingowej Podstawy matematyki . Z pewnością ale z odpowiedzi na to pytanie podejrzewam , że nie wiadomo, czy ⊕ P ⊆ P P (inaczej P P byłaby jedną z możliwych odpowiedzi na to pytanie). Jeśli nie wiadomo, czy istnieje separacja wyroczni?P⊕P⊆P#P=PPPP⊕P⊆P#P=PPPP^{\oplus P} \subseteq …
1
Czy istnieje algorytm kwantowy NC do obliczania GCD?
Z uwagi na jedno z moich pytań dotyczących MathOverflow mam wrażenie, że kwestia dotycząca GCD będąc w vs. P jest zbliżona do kwestii dotyczącej Integer faktoryzacji Będąc w P vs. N P .NCNC\mathsf{NC}PP\mathsf{P}PP\mathsf{P}NPNP\mathsf{NP} Czy istnieje coś takiego jak „quantum algorytm” dla GCD jak jest kwantowa wielomian czas ( B Q …
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.