Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

1
Algorytmy kwantowe do obliczeń QED związane ze stałymi drobnych struktur
Moje pytanie dotyczy algorytmów kwantowych do obliczeń QED (elektrodynamiki kwantowej) związanych ze stałymi drobnych struktur. Takie obliczenia (jak mi wyjaśniono) sprowadzają się do obliczenia szeregu podobnego do Taylora gdzie α jest stałą drobnej struktury (około 1/137), a c k jest wkładem diagramów Feynmana z k- pętlami. ∑ckαk,∑ckαk,\sum c_k\alpha^k,αα\alphackckc_kkkk To pytanie …
1
Izomorfizm Bermana-Hartmanisa dla NP
Korzystając z modelu rzeczywistej pamięci RAM / BSS, mamy klasę NP R (gdzie BSS to model Blum-Shub-Smale komputera z operacjami nad rzeczywistością). Mamy kompletne problemy z NP R. Pytanie zatem, czy istnieje analogia do hipotezy Bermana Hartmanisa dla klasy NP R ? Oczywiście postawione tutaj pytanie zależy od modelu - …
1
Problem występuje w P tylko wtedy, gdy P! = NP
Czy są jakieś problemy, które można rozwiązać w czasie wielomianowym tylko wtedy, gdy P! = NP, a w innym przypadku rozwiązać (powiedzmy) ?O ( 2n)O(2)n)O(2^n) Prostym przykładem byłoby: Jeśli P! = NP, oblicz test pierwszeństwa dla losowej liczby n-bitowej, w przeciwnym razie oceń losową pozycję najgorszego przypadku w uogólnionych szachach …
1
Czy rachunek afiniczny lambda może rozwiązać każdy problem w P?
W Zaawansowanych tematach w typach i językach programowania w rozdziale o podstrukturalnych systemach typów wspomniano, że „starannie spreparowany” rachunek afiniczny lambda z kombinatorem rekurencyjnym dla list może wpisywać tylko terminy, które mają wielomianowy czas działania (nie przedstawić dowód ze względu na złożoność). Byłoby to bardzo interesujące, gdybyśmy mogli rozwiązać każdy …
1
Ukryta ścieżka w kwadratowych siatkach
Natknąłem się na otwarty problem postawiony przez Davida Eppsteina i jestem zainteresowany jego złożonością. Doszedł do wniosku, że jest kompletny NP. Dane wejściowe: przez macierzy zer i jedynek, sekwencja zer i jedyneknnnnnnn2n2n^2 Pytanie: Czy istnieje ścieżka przez sąsiednie wpisy macierzy, obejmujące każdy wpis macierzy dokładnie raz, a wartości pasują do …
2
Kompletność obejmująca drzewa
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 tego pytania jest to, że odpowiadającym problemem dla drzew niezależności jest …
1
,
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ą między a P F …
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.