Pytania otagowane jako complexity-classes

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

2
Dlaczego uważamy, że PSPACE ≠ EXPTIME?
Mam problem z intuicyjnym zrozumieniem, dlaczego ogólnie uważa się, że PSPACE różni się od EXPTIME. Jeśli PSPACE jest zbiorem problemów możliwych do rozwiązania w wielomianu kosmicznym w wielkości wejściowej fa( n )f(n)f(n) , to w jaki sposób może istnieć klasa problemów, które doświadczają większego wybuchu czasu wykładniczego i nie wykorzystują …
3
Czy oznacza, że?
Czy to możliwe, że a liczność jest taka sama jak liczność ? Czy też oznacza, że i muszą mieć różne liczności?P N P P ≠ N P P N PP≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}P≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}
1
Klasy złożoności związane z listowaniem wszystkich rozwiązań?
Czytałem pytanie na Stack Overflow, pytając, czy to NP- twarde, aby wymienić wszystkie proste cykle na wykresie zawierającym określony węzeł i przyszło mi do głowy, że nie mogę wymyślić żadnej istniejącej klasy złożoności, która byłaby odpowiednia dla mówiąc o problemach z formularzem „wymień wszystkie rozwiązania tego problemu”. Klasa NP w …
1
Dowód twierdzenia Karpa-Liptona
Próbuję zrozumieć dowód twierdzenia Karp-Lipton, jak stwierdzono w książce „Złożoność obliczeniowa: nowoczesne podejście” (2009). W szczególności ta książka stwierdza, co następuje: Twierdzenie Karpa-Liptona Jeśli NP , to PH .P ∖ p o l y⊆⊆\subseteq P∖polyP∖polyP_{\backslash poly} =Σp2=Σ2p= \Sigma^p_2 Dowód: Zgodnie z twierdzeniem 5,4, w celu wykazania pH , to wystarczy, …
2
Czy istnieją ustalone klasy złożoności z liczbami rzeczywistymi?
Niedawno student poprosił mnie o sprawdzenie dla nich dowodu twardości NP. Dokonali redukcji zgodnie z: Zmniejszam ten problem P′P′P' którym wiadomo, że jest NP-kompletny do mojego problemu PPP (z redukcją wielokrotnego wielokrotności jeden), więc PPP jest NP-twardy. Moja odpowiedź brzmiała w zasadzie: Ponieważ PPP ma instancje z wartościami z RR\mathbb{R} …
2
Kilka pytań na temat obliczeń równoległych i klasy NC
Mam wiele powiązanych pytań dotyczących tych dwóch tematów. Po pierwsze, większość tekstów złożoności tylko tuszować klasę . Czy istnieje dobry zasób, który bardziej szczegółowo omawia badania? Na przykład coś, co omawia wszystkie moje pytania poniżej. Ponadto, jestem przy założeniu, że N C nadal widzi ilość godziwą badań ze względu na …
3
P, NP i specjalistyczne maszyny Turinga
Jestem w pewnym sensie nowy, ale bardzo zainteresowany dziedziną obliczeń i teorii złożoności, i chcę wyjaśnić moje rozumienie, w jaki sposób klasyfikować problemy i jak silnie problemy odnoszą się do maszyny używanej do ich rozwiązywania. Moje zrozumienie Standardowa maszyna Turinga - maszyna Turinga, która ma skończony alfabet, skończoną liczbę stanów …
1
Czy są jakieś znane problemy z kompletnym AM / czy kompletne AM jest dobrze zdefiniowane?
Jestem ciekawy, czy w klasie złożoności Arthura-Merlina występują jakieś kompletne problemy. Graph Non-Isomorphism (GNI) wydaje się być kanonicznym przykładem problemu w AM, ale prawdopodobnie nie jest kompletny. Chyba zastanawiam się również, czy „kompletny” problem jest dobrze zdefiniowany dla AM. Ponieważ AM = BP.NP, wydaje się, że przejście na „redukcję” do …
1
Co to jest klasa złożoności
Co oznacza klasa złożoności ? Wiem, że jest klasą złożoności, która zawiera języki dla których istnieje wielomianowa niedeterministyczna maszyna Turinga taka, że iff liczba akceptujących stanów maszyny na wejściu jest nieparzysta. ⊕ P A M x ∈ A M x⊕P⊕P⊕P⊕P\oplus P^{\oplus P}⊕P⊕P\oplus PAAAMMMx∈Ax∈Ax \in AMMMxxx Ale co oznacza ? Po …
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.