Pytania otagowane jako complexity-classes

Pytania o relacje między klasami złożoności.

1
Dlaczego NP jest w EXPTIME?
Czy istnieje prosty sposób, aby dowiedzieć się, dlaczego NP jest w WYGODZIE? Wydaje mi się a priori możliwe, że może istnieć problem, który wymaga czasu nadwykładniczego do rozwiązania, ale którego rozwiązanie można zweryfikować w czasie wielomianowym.
5
Czy wszystkie problemy z całkowitym programowaniem liniowym są trudne?
Jak rozumiem, problem przypisania występuje w P, ponieważ węgierski algorytm może go rozwiązać w czasie wielomianowym - O (n 3 ). Rozumiem również, że problem z przypisaniem jest całkowitym problemem programowania liniowego , ale strona Wikipedii stwierdza, że ​​jest to NP-Hard. Dla mnie oznacza to, że problem przypisania jest w …
1
Czy są jakieś naturalne problemy z
Wiem, że skwantyfikowany problem z formułą logiczną dla formuły gdzie nie zawiera kwantyfikatorów i tylko zmienne jest przykładem . Zastanawiam się jednak, czy są jakieś naturalne problemy, o których wiadomo, że są , tak jak obwodu jest naturalnym (szczegóły w hierarchii wielomianowej )?ψ = ∀ x1… ∀ xn∃ Y1… ∃ …
2
Czy
Jeśli hierarchia zapada się na swój drugi poziom (według twierdzenia Karpa-Liptona). Ale co z N P i C o N P ?RP=NPRP=NP\sf RP = NPNPNP\sf NPcoNPcoNP\sf coNP Starałem się udowodnić, że zawarty jest w N P (drugi kierunek jest trywialne, jeśli R P = N P ), ale bez skutku, …
1
Jak wyglądają klasy złożoności, jeśli zastosujemy redukcje Turinga?
Do rozumowania takich rzeczy, jak kompletność NP, zwykle stosujemy redukcje wielokrotne jeden (tj. Redukcje Karp). Prowadzi to do takich zdjęć: (zgodnie ze standardowymi przypuszczeniami). Jestem pewien, że wszyscy znamy tego rodzaju rzeczy. Jakie otrzymamy zdjęcie, jeśli będziemy pracować z redukcjami Turinga (tj. Redukcjami Cooka)? Jak zmienia się obraz? PNPPNPP^{NP}NPNPNPcoNPcoNPcoNPPNPPNPP^{NP}NPNPNP P⊂PNP⊂PH⊂PSPACEP⊂PNP⊂PH⊂PSPACEP …
1
Intuicja stojąca za relatywizacją
Biorę kurs na złożoność obliczeniową. Mój problem polega na tym, że nie rozumiem metody relatywizacji . Próbowałem znaleźć odrobinę intuicji w wielu podręcznikach, jak dotąd niestety bez powodzenia. Będę wdzięczny, jeśli ktoś może rzucić światło na ten temat, abym mógł kontynuować sam. Kilka kolejnych zdań to pytania, a moje przemyślenia …
3
Dowód, że jeżeli
Naprawdę chciałbym, abyś pomógł mi udowodnić, co następuje. Jeżeli N T i m e ( n100)⊆DTime(n1000)NTime(n100)⊆DTime(n1000)\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000}) , a następnie P=NPP=NP\mathrm{P}=\mathrm{NP} . Tutaj NTime(n100)NTime(n100)\mathrm{NTime}(n^{100}) jest klasą wszystkich języków, o których decyduje niedeterministyczna maszyna Turinga w czasie wielomianowym i jest klasą wszystkich języków, o których decyduje deterministyczna maszyna Turinga w …
3
Konkretne zrozumienie różnicy między definicjami PP i BPP
Jestem zdezorientowany co do definicji PP i BPP . Załóżmy, że jest charakterystyczną funkcją języka . M być probabilistyczną Maszyną Turinga. Czy następujące definicje są poprawne:χχ\chiLL\mathcal{L} BPP={L:Pr[χ(x)≠M(x)]≥12+ϵ∀x∈L, ϵ>0}BPP={L:Pr[χ(x)≠M(x)]≥12+ϵ∀x∈L, ϵ>0}BPP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] \geq \frac{1}{2} + \epsilon \quad \forall x \in \mathcal{L},\ \epsilon > 0 \} PP={L:Pr[χ(x)≠M(x)]>12}PP={L:Pr[χ(x)≠M(x)]>12}PP =\{\mathcal{L} :Pr[\chi(x) \ne …
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.