Pytania otagowane jako complexity-classes

Klasy złożoności obliczeniowej i ich relacje

8
Jaka klasa złożoności jest najbardziej związana z tym, co ludzki umysł może szybko osiągnąć?
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 (analogiczną do zadania P). Ale czy NP to naprawdę …
2
Czy można wzmocnić P = NP poza P = PH?
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 przechwytuje wielomianową hierarchię czasu PH, a FO (LFP) …
4
Jakie są konsekwencje
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(log2⁡n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Wiadomo również, że polyL≠PpolyL≠P\mathsf{polyL} \neq \mathsf{P}ponieważ ten drugi ma całkowite problemy w przestrzeni logarytmicznej, wielokrotne redukcje jeden-jedynki, podczas gdy ten drugi nie (ze względu na twierdzenie o …
4
Przykłady, w których wyjątkowość rozwiązania ułatwia znalezienie
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 nieprawdopodobne, że wszystkie U P -Problemy są P …
7
Co wiemy o możliwych do udowodnienia poprawnych programach?
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 „kompilatorem certyfikującym” (znalazłem go tutaj ): kompilatorem kompilującym język programowania, w którym …
3
Czy implikuje ?
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 , czy jest to tylko duży krok w kierunku tego celu?P≠NPP≠NPP \neq NP
3
Wyjaśnienie klas P i NP za pomocą rachunku lambda
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 modelu obliczeń), ale nigdy nie widziałem wyjaśnienia …
2
Klasy złożoności semantycznej a składniowej
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ć niezwykłą właściwość, która na wszystkich wejściach albo …
5
Nieuzasadniona moc niejednolitości
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 strony, jeśli po prostu dodamy niejednolitość do , uzyskując , wówczas intuicja jest …
3
złożoność największego wspólnego dzielnika (gcd)
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ć referencje? W tym pytaniu nie interesują mnie przede wszystkim asymptotyczne …
2
Konsekwencje
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” (Bennett i in. 1997): jeśli odrzucisz strukturę problemu i po prostu weźmiesz …
1
vs?
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 instancji) i (ekwiwalent kwantowy z ) zamiast.B Q PBQPBQPQ MZAQMAQMAN.P.NPNP Moje pytania: 1) Czy …
3
Założenia antologii złożoności
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ń, albo hipotezy losowej wyroczni. Najważniejszym i powszechnie uznawanym założeniem jest to, …
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.