Pytania otagowane jako complexity-classes

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

2
Jaka jest równoważna definicja mP / poli w odniesieniu do maszyny Turinga?
P / poly to klasa problemów decyzyjnych rozwiązanych przez rodzinę obwodów boolowskich wielkości wielomianowych. Alternatywnie można go zdefiniować jako wielomianową maszynę Turinga, która otrzymuje ciąg porady, który jest wielomianem wielkości w n, i który opiera się wyłącznie na rozmiarze n. mP / poli to klasa problemów decyzyjnych rozwiązanych przez rodzinę …
2
Czy L ma definicję obwodów?
Wiele klas złożoności zdefiniowanych za pomocą maszyn Turinga ma definicje w kategoriach jednorodnych obwodów. Na przykład P można również zdefiniować za pomocą obwodów o jednorodnych rozmiarach wielomianowych, podobnie BPP, NP, BQP itp. Można zdefiniować za pomocą obwodów jednorodnych. Czy istnieje oparta na obwodzie definicja L? Oczywistym pomysłem byłoby dopuszczenie obwodów …
1
Dlaczego te dwie definicje PPAD są równoważne?
Klasa złożoności PPAD jest zwykle definiowana przez stwierdzenie, że Koniec linii jest kompletny z PPAD. Koniec linii to problem z wyszukiwaniem. Dane wejściowe składają się z ukierunkowanego wykresu, w którym każdy węzeł ma co najwyżej stopień i stopień 1. Wykres jest podawany przez funkcję obliczeniową wielomianową która zwraca poprzednika i …
3
Gra na kilku wykresach
Rozważ następującą grę na ukierunkowanym wykresie ważonym solGG z chipem w pewnym węźle. Wszystkie węzły solGG oznaczone są literą A lub B. Jest dwóch graczy Alice i Bob. Celem Alicji (Bob) jest przesunięcie czipa do węzła oznaczonego literą A (B). Początkowo Alice i Bob mają odpowiednio mZAmAm_A i mbmBm_B dolarów. …
1
Złożoność testowania, jeśli dwa zestawy
Wyobraźmy sobie, że mamy dwa zestawy rozmiarów punktów . Jaka jest (czasowa) złożoność testowania, jeśli różnią się one tylko rotacją? : istnieje macierz rotacji taka, że ?mmmX,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^nOOT=OTO=IOOT=OTO=IOO^T=O^TO=IX=OYX=OYX=OY Istnieje tutaj problem reprezentowania rzeczywistych wartości - dla uproszczenia załóżmy, że dla każdej współrzędnej istnieje (krótki) wzór algebraiczny, tak że koszt podstawowych …
1
Hierarchie czasu w DSPACE (O (s)))
Twierdzenie o hierarchii czasu stwierdza, że ​​maszyny Turinga mogą rozwiązać więcej problemów, jeśli mają (wystarczająco) więcej czasu. Czy to w jakiś sposób się utrzymuje, jeśli przestrzeń jest asymptotycznie ograniczona? Jak DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n), O(s(n))) odnosi się do DTISP(f(n),O(s(n)))DTISP(f(n),O(s(n)))\textrm{DTISP}(f(n), O(s(n))) jeśli fgfg\frac{f}{g} rośnie wystarczająco szybko? Ja szczególnie zainteresowany w przypadku, s(n)=ns(n)=ns(n) = n …
1
Duże klasy zawierające LOGSPACE, dla których ścisłe włączenia nie są znane
Strona wikipedii na PSPACE wspomina, że ​​włączenie nie jest znane jako ścisłe (niestety bez odnośników).NL⊂PHNL⊂PHNL\subset PH P1: Co z i - czy są one znane jako ścisłe?L⊂PHL⊂PHL\subset PHL⊂P#PL⊂P#PL\subset P^{\#P} P2: Jeśli nie, czy istnieje ustalona klasa która zawiera i dla której nie wiadomo, czy włączenie jest ścisłe?CCCP#PP#PP^{\#P}L⊂CL⊂CL\subset C P3: Czy …
1
Czy różni się od ?
Czy możemy udowodnić, że dla każdego języka który nie jest -hard (zakłada to ), ? Alternatywnie, czy można to udowodnić przy jakichkolwiek uzasadnionych założeniach?L∈NPL∈NPL\in\mathsf{NP}NPNP\mathsf{NP}P≠NPP≠NP\mathsf P \ne \mathsf{NP}PL≠PSATPL≠PSAT\mathsf{P}^L \ne \mathsf{P}^{\text{SAT}}
1
Czy twierdzenie Kannana implikuje, że NEXPTIME ^ NP ⊄ P / poly?
Czytałem artykuł Buhrmana i Homera „Obwody wielobiegunowe, Prawie rzadkie wyrocznie i hierarchia wykładnicza” . Na dole strony 2 zauważają, że wyniki sugerują, że nie ma obwodów wielomianowych. Wiem, że w wykładniczej hierarchii czasu to po prostu , a także wiem, że wynikiem jest to, że tak, że . Oczywiście twierdzenie …
1
jako wyrocznia
Czy N P.N P.∩c o N P= N P.N.P.N.P.∩dooN.P.=N.P.\mathsf{NP^{NP \,\cap\, coNP}=NP}trzymać? Najwyraźniej N P.N P.≠ N P.N.P.N.P.≠N.P.\mathsf{NP^{NP}\neq NP} , ale wydaje mi się, że N P ∩ c o N PN.P.∩dooN.P.\mathsf{NP\cap coNP} jest „deterministyczna”, co pozwala mi wierzyć, że to prawda. Czy istnieje prosty dowód (a może tylko z definicji)?
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.