Klasy złożoności obliczeniowej i ich relacje
Norbert Blum opublikował niedawno 38-stronicowy dowód, że . Czy to jest poprawne?P.≠ N.P.P≠NPP \ne NP Także na temat: gdzie jeszcze (w Internecie) omawia się jego poprawność? Uwaga: zakres tego tekstu pytania zmienił się z czasem. Szczegóły znajdują się w komentarzach do...
Zastanawiam się nad tym pytaniem. Kiedy ludzie opisują problem P vs. NP, często porównują NP klasy do kreatywności. Zauważają, że skomponowanie symfonii jakości Mozarta (analogicznej do zadania NP) wydaje się znacznie trudniejsze niż sprawdzenie, czy już skomponowana symfonia ma jakość Mozarta...
W złożoności opisowej Immerman ma Wniosek 7.23. Następujące warunki są równoważne: 1. P = NP. 2. Przekroczone, uporządkowane struktury, FO (LFP) = SO. Można to uznać za „wzmocnienie” P = NP do równoważnego wyrażenia w (przypuszczalnie) większych klasach złożoności. Zauważ, że SO...
Wiemy, że L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} i że L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , gdzie L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Wiadomo również, że...
O ile rozumiem, program teorii geometrycznej złożoności próbuje oddzielić , udowadniając, że permament macierzy o złożonej wartości jest znacznie trudniejszy do obliczenia niż wyznacznik.VP≠VNPVP≠VNPVP \neq VNP Pytanie, które zadałem po przejrzeniu dokumentów GCT: Czy to natychmiast oznaczałoby ,...
Klasa złożoności składa się z tych N P -Problemy że może być określana przez wielomian czasu niedeterministycznych maszynie Turinga, który ma co najwyżej jedną ścieżkę akceptacji obliczeniowej. Oznacza to, że rozwiązanie, jeśli w ogóle, jest wyjątkowe w tym sensie. Uważa się wysoce...
Coraz większa złożoność programów komputerowych i coraz ważniejsza pozycja komputerów w naszym społeczeństwie sprawia, że zastanawiam się, dlaczego nadal nie używamy zbiorowo języków programowania, w których musisz formalnie udowodnić, że kod działa poprawnie. Uważam, że termin ten jest...
We wstępie i wyjaśnieniach klasy złożoności P i NP często podawane przez maszynę Turinga. Jednym z modeli obliczeń jest rachunek lambda. Rozumiem, że wszystkie modele obliczeń są równoważne (i jeśli możemy wprowadzić coś w kategoriach maszyny Turinga, możemy wprowadzić to w kategoriach dowolnego...
W swojej książce „Computational Complexity” Papadimitriou pisze: RP jest w pewnym sensie nową i niezwykłą klasą złożoności. Żadna żadna wieloznacznie niedeterministyczna maszyna Turinga nie może być podstawą do zdefiniowania języka w RP. Aby maszyna N mogła zdefiniować język w RP , musi mieć...
Z punktu widzenia zdrowego rozsądku łatwo jest uwierzyć, że dodanie niedeterminizmu do znacznie rozszerza jego moc, tj. jest znacznie większy niż . W końcu niedeterminizm umożliwia wykładniczy paralelizm, który niewątpliwie wydaje się bardzo silny. PP\mathsf{P}NPNP\mathsf{NP}PP\mathsf{P} Z drugiej...
Jako amator TCS czytam popularny materiał wprowadzający na temat komputerów kwantowych. Oto kilka podstawowych elementów informacji, których nauczyłem się do tej pory: Komputery kwantowe nie są znane z rozwiązywania problemów NP-zupełnych w czasie wielomianowym. „Magia kwantowa nie wystarczy”...
Rozważ następujący problem zliczania (lub związany z tym problem decyzyjny): Biorąc pod uwagę dwie dodatnie liczby całkowite zakodowane w systemie binarnym, oblicz ich największy wspólny dzielnik (gcd). Jaka jest najmniejsza klasa złożoności, w której występuje ten problem? Czy możesz podać...
Centralnym problemem teorii złożoności jest zapewne vs .P.PPN.P.NPNP Ponieważ natura jest kwantowa, bardziej naturalne wydaje się rozważenie klas (tj. Problemów decyzyjnych rozwiązanych przez komputer kwantowy w czasie wielomianowym, z prawdopodobieństwem błędu co najwyżej 1/3 dla wszystkich...
To pytanie dotyczy problemów, dla których istnieje duża otwarta luka złożoności między znaną dolną i górną granicą, ale nie z powodu otwartych problemów dotyczących samych klas złożoności. Mówiąc ściślej, powiedzmy, że problem ma klasy przerw (z A ⊆ B , nie jednoznacznie zdefiniowane), jeśli A...
W artykule Losowa hipoteza Oracle jest fałszywa , autorzy (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan i Rohatgi) omawiają implikacje hipotezy losowo-wyroczni . Twierdzą, że niewiele wiemy o separacjach między klasami złożoności, a większość wyników wymaga albo przyjęcia rozsądnych założeń,...
Często cytowane jest filozoficzne uzasadnienie, by wierzyć, że P! = NP nawet bez dowodu. Inne klasy złożoności mają dowody na ich odrębność, ponieważ jeśli nie, miałyby „zaskakujące” konsekwencje (takie jak upadek hierarchii wielomianowej). Moje pytanie brzmi: jaka jest podstawa przekonania, że...
Wokół jest mnóstwo problemów z kompletnym NP i źródła je zbierające, np. Patrz książka Garey i Johnsona. Byłbym również zainteresowany, aby zobaczyć listę problemów uzupełniających NEXP. Czy jest dostępny? Ponieważ zakładam, że nie ma, otwieram to pytanie (czy to ma być wiki społeczności? Nie wiem...
Jakie byłyby paskudne konsekwencje NP = PSPACE? Dziwi mnie, że nie znalazłem nic na ten temat, biorąc pod uwagę, że zajęcia te należą do najbardziej znanych. W szczególności, czy miałoby to jakiekolwiek konsekwencje dla klas
Przypuszcza się, że ponieważ odwrotność oznaczałaby . Twierdzenie Ladnera stwierdza, że jeśli a następnie . Wydaje się jednak, że dowód nie uogólnia na więc możliwość ie wydaje się otwarty.NP⊈P/polyNP⊈P/poly\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}PH=Σ2PH=Σ2\mathsf{PH} =...
Załóżmy, że P = NP jest prawdziwe. Czy byłoby zatem jakieś praktyczne zastosowanie do budowy komputera kwantowego, takie jak szybsze rozwiązywanie określonych problemów, czy też takie ulepszenie byłoby nieistotne w związku z faktem, że P = NP jest prawdziwe? Jak scharakteryzowałbyś poprawę...