Następujące pytanie jest związane z optymalności Bellmana-Forda - najkrótsza droga algorytm programowania dynamicznego (patrz ten post dla połączenia). Pozytywna odpowiedź sugerowałaby również, że minimalny rozmiar monotonicznego niedeterministycznego programu do rozgałęziania dla problemu STCONN...
Jestem zainteresowany niewielkim uogólnieniem DFA. Jak zwykle mamy ustawiony stan , skończony alfabet , działanie zdefiniowane na przez i stan początkowy ; lecz w zwykłym zestawem terminali wziąć rodziny podzbiorów . Wielojęzyczny DFA jest wtedy krotkąQQQΣΣ\SigmaΣ∗Σ∗\Sigma^*QQQδ:Q×Σ→Qδ:Q×Σ→Q\delta...
Piszę pracę magisterską w CS i pracuję nad analizą aliasów. To, co mnie interesuje, to intraproceduralne, wrażliwe na przepływ analizy must-may-may-alias dla języków podobnych do Java. Poszukuję tekstów, które szczegółowo opisują podstawy tego tematu, ale nie udało mi się znaleźć niczego naprawdę...
W przemówieniu Razborowa opublikowano dziwne oświadczenie. Jeśli FACTORING jest trudny, to małe twierdzenie Fermata nie jest możliwe do udowodnienia w S12S21S_{2}^{1} . Co to jest S12S21S_{2}^{1} i dlaczego aktualnych dowodów nie ma w S12S21S_{2}^{1} ?
BPPBPP\mathsf{BPP} iZ P PZPP\mathsf{ZPP} to dwie podstawowe probabilistyczne klasy złożoności. B P PBPP\mathsf{BPP} jest klasą języków ustaloną przez probabilistyczne algorytmy Turinga w czasie wielomianowym, w których prawdopodobieństwo zwrotu nieprawidłowej odpowiedzi przez algorytm jest...
Zdefiniujmy klasę funkcji w zbiorze bitów. Napraw dwa rozkłady które są „rozsądnie” różne od siebie (jeśli chcesz, ich odległość wariacyjna wynosi co najmniej lub coś podobnego).nnnp,qp,qp, qϵϵ\epsilon Teraz każda funkcja w tej klasie jest zdefiniowana przez zbiór indeksów i jest oceniana w...
W złożoności komunikacyjnej domniemanie log-rank stwierdza, że c c ( M) = ( logr k ( M) )O ( 1 )cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Gdzie jest złożoność komunikacji M ( x , y ) , a r k ( M ) jest rangę M (jako matrycy) w liczb rzeczywistych.c c ( M)cc(M)cc(M)M.( x , y)M(x,y)M(x,y)r k...
Klasa złożoności jest zdefiniowana następująco (z Wikipedii ):SP2S.2)P.\textrm{S}_2^\textrm{P} Język znajduje się w S P 2, jeśli istnieje predykat P wielomianowy taki, żeLL.LSP2S.2)P.S_2^PPP.P Jeśli , to istnieje y takie, że dla wszystkich z , P ( x , y , z ) = 1x ∈ L.x∈L.x \in LyyyzzzP.( x...
Czy istnieje naturalna klasa formuł CNF - najlepiej taka, która była wcześniej badana w literaturze - o następujących właściwościach:doCC jest łatwym przypadkiem SAT, takim jak np. Horn lub 2-CNF, tj. Członkostwo w C można badać w czasie wielomianowym, a wzory F ∈ C można badać pod kątem...
Jakiego algorytmu możemy użyć do znalezienia wszystkich pierwiastków całkowitych wielomianu o współczynnikach całkowitych?fa( x )f(x)f(x) Zauważyłem, że Sage może znaleźć pierwiastki w ciągu kilku sekund, nawet jeśli wszystkie współczynniki są bardzo duże. Jak to zrobić?fa( x...
Czy są znane algorytmy dla następującego problemu, które pokonały naiwny algorytm? Dane wejściowe: system o nierówności liniowych.A x ≤ bZAx≤bAx \le bmmm Wynik: wykonalne rozwiązanie jeśli takie istnieje.x∗∈ { 0 , 1 }nx∗∈{0,1}nx^*\in \{0,1 \}^n Załóżmy, że i mają wpisy liczb całkowitych....
Czy izomorfizm grafów (problem decyzyjny) znajduje się w ? Tutaj to klasa problemów decyzyjnych akceptowanych przez jednoznaczną maszynę Turinga (patrz zoo złożoności ).UP∩coUPUP∩coUP\mathsf{UP}\cap
Słyszałem o przybliżonym zabarwieniu wykresu, ale nie mogę znaleźć źródła. Wynik to: Dla każdego stałego istnieje wystarczająco duża taki sposób, że barwienia -colorable wykres z kolorów NP-trudne.hhhkkkkkkh khkhk Czy ktoś mógłby mi wskazać odpowiedni
Próbowałem zrozumieć te zajęcia, ale zawsze byłem zdezorientowany ... pytania są następujące: Jaki jest związek między a # P , w szczególności czy jest to pytanie otwarte?faN.P.faN.P.FNP# P#P.\#P Jaki jest stosunek i N P ? czy to pytanie jest otwarte?⊕ P.⊕P.\oplus PN.P.N.P.NP A co z relacją...
Jak trudny jest problem Ustaw okładkę, jeśli liczba elementów jest ograniczona przez jakąś funkcję (np. ), gdzie jest rozmiarem wystąpienia problemu. Formalnie,nlognlogn\log nnnn Niech i gdzie i . Jak trudno jest rozwiązać następujący problemF = { S 1 , ⋯ , S n } S i ⊆ U m = O ( log n )U= { e1,...
Drzewo opinające wykresu nazywane jest drzewem kompletności, jeśli zbiór jego liści indukuje całkowity podrozdział na grafie gospodarza. Biorąc pod uwagę wykres i liczbę całkowitą , jaka jest złożoność decyzji, czy zawiera drzewo kompletności z co najwyżej liści?GsolGkkkGGGkkk Powodem zadawania...
Biorąc pod uwagę zbiór punktów w d wymiarowej przestrzeni euklidesowej, problemem jest ustalenie, czy wypukłe kadłuba zawiera piłka jednostki skupione na pochodzenie.nnnrered Czy to problem w NP? Jest w ko-NP, ponieważ można dać punkt w kuli poza wypukłym kadłubem jako świadek i zweryfikować...
Większość asystentów dowodowych ma sformalizowaną koncepcję „zbioru skończonego”. Te formalizacje różnią się jednak bardzo dziko (choć można mieć nadzieję, że wszystkie są w zasadzie równoważne!). Nie rozumiem w tym momencie zajmowanej przestrzeni projektowej oraz jakie są zalety i wady każdej...
Mam następujący problem: Dane wejściowe: dwa zestawy przedziałów i (wszystkie punkty końcowe są liczbami całkowitymi). Pytanie: czy istnieje biotonia monotoniczna ?T f : S → TS.S.ST.T.Tfa: S→ T.fa:S.→T.f:S \to T Bijection jest monotoniczne WRT kolejnością włączenie do i . T ∀ X ⊆ Y ∈ S , f ( X )...
Rozważ niepusty język ciągów binarnych o długości . Mogę opisać za pomocą obwodu logicznego z wejściami i jednym wyjściem takim, że jest prawdą, iff : jest to dobrze znane.n L C n C ( w ) w ∈ L.L.LLnnnL.LLdoCCnnndo( w )C(w)C(w)w ∈ L.w∈Lw \in L Jednakże, chce reprezentować z logicznego obwodu z...