Pytania otagowane jako complexity-classes

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

3
Co dowody na to, że
Co dowody na to, że ?c o R P≠ N.P.coRP≠NPcoRP \neq NP jest klasą języków, dla których istnieje probabilistyczna maszyna Turinga, która działa w czasie wielomianowym i zawsze odpowiada Tak na dane wejściowe należące do języka i odpowiada Nie z prawdopodobieństwem co najmniej połowy na dane wejściowe nienależące do języka …
1
Naturalni kandydaci na NP-E i E-NP
Od wczesnych lat 70. wiadomo, że i nie są równe (ponieważ nie jest zamknięty w czasie wielomianowym wiele -jedna redukcja, w przeciwieństwie do ). O ile mi wiadomo, wciąż pozostaje otwarte, czy jedna klasa jest podzbiorem drugiej, czy też są nieporównywalne, co oznacza, że i są niepuste.NPNP{\bf NP}E=DTIME(2O(n))E=DTIME(2O(n)){\bf E}=DTIME(2^{O(n)})EE{\bf E}NPNP{\bf …
2
Czy istnieje problem obliczeniowy, który występuje w quasi-wielomianowym czasie, ale (być może) go nie ma
Czas quasi-wielomianowy, w skrócie QP, jest klasą złożoności na deterministycznej maszynie Turinga. Oto dokładna definicja: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp Podczas gdy βP jest klasą złożoności o ograniczonym niedeterminizmie. Oto dokładna definicja: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap Łatwo zauważyć, że dowolna maszyna βP może być symulowana przez maszynę QP, a mianowicie βP ⊆⊆\subseteq QP. Ale czy mamy przykład …
1
2-NEXPTIME-zupełne problemy
Mamy problem i znaleźliśmy algorytm, który wydaje się być 2-sekundowy. Chciałbym znaleźć znane problemy z niepełnym czasem 2, aby znaleźć dolną granicę. W literaturze znalazłem głównie dwa takie problemy: czy PCP jako rozwiązanie o rozmiarze mniejszym niż 2)2)n2)2)n2^{2^n} i problem uprawy roli dla kwadratu wielkości 2)2)n2)2)n2^{2^n} Jednak nie byłem w …
2
Dokładna złożoność problemu w
Pozwolić xi∈{−1,0,+1}xi∈{−1,0,+1}x_i \in \{-1,0,+1\} dla i∈{1,…,n}i∈{1,…,n}i \in \{1,\ldots,n\}, z obietnicą, że x=∑ni=1xi∈{0,1}x=∑i=1nxi∈{0,1}x = \sum_{i=1}^n{x_i} \in \{0,1\} (gdzie suma się skończyła ZZ\mathbb{Z}). Jaka jest złożoność ustalenia, czyx=1x=1x = 1? Zauważ, że w trywialny sposób leży problem ∩m≥2AC0[m]∩m≥2AC0[m]\cap_{m \geq 2}{\mathsf{AC}^0[m]} ponieważ x≡1modmx≡1modmx \equiv 1\bmod{m}iff . Pytanie brzmi: czy problem leży w ? …
2
Konsekwencje OWF dla złożoności
Powszechnie wiadomo, że istnienie funkcji jednokierunkowych jest konieczne i wystarczające dla dużej części kryptografii (podpisy cyfrowe, generatory pseudolosowe, szyfrowanie kluczem prywatnym itp.). Moje pytanie brzmi: jakie są teoretyczne konsekwencje istnienia funkcji jednokierunkowych? Na przykład sugerują to OWFN P ≠ PN.P.≠P.\mathsf{NP}\ne\mathsf{P}, B P P = PbP.P.=P.\mathsf{BPP}=\mathsf{P}, i C Z K = …
2
Czy adiabatyczne obliczenia kwantowe są tak potężne jak model obwodowy?
Znaczna część literatury obliczeń kwantowych koncentruje się na modelu obwodu. Adiabatyczne obliczenia kwantowe nie polegają na zastosowaniu sekwencji operatorów jednostkowych, ale na zmianie zależnego od czasu hamiltonianu. Szukam wglądu w którekolwiek z poniższych. Czy adiabatyczne obliczenia kwantowe są tak potężne jak model obwodowy, czy też są z natury mniej wydajne? …
1
Na
Wiemy to L⊆NL⊆P⊆NPL⊆NL⊆P⊆NP\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}. Z twierdzenia SavitchaNL⊆L2NL⊆L2\mathcal{N\!L}\subseteq\mathcal{L}^2, a od Space Hierarchy Teorem, L≠L2L≠L2\mathcal{L}\neq\mathcal{L}^2. Ponieważ nie wiemy, czyL≠PL≠P\mathcal L\neq\mathcal Pnie wiemy czy L2⊆PL2⊆P\mathcal L^2\subseteq\mathcal Pczy wiemy o tym L2⊈PL2⊈P\mathcal L^2\not\subseteq\mathcal P? Czy ktoś próbował udowodnić, że ? Jakie są najnowsze wyniki lub wysiłki w ten sposób? Próbowałem napisać ankietę na ten …
1
Mogą
Pozwolić ATISP(f(n),g(n))ATISP(f(n),g(n))\mathsf{ATISP}(f(n), g(n)) być klasą języków ustaloną przez naprzemienne maszyny Turinga, które zatrzymują się w czasie f(n)f(n)f(n) używając przestrzeni g(n)g(n)g(n). PozwolićAALTSP(f(n),g(n))AALTSP(f(n),g(n))\mathsf{AALTSP}(f(n), g(n)) być klasą języków ustaloną przez naprzemienne używanie maszyn Turinga f(n)f(n)f(n) alternacje i przestrzeń g(n)g(n)g(n). Ruzzo udowodnił , żeNCk=ATISP(logkn,logn)NCk=ATISP(logk⁡n,log⁡n)\mathsf{NC}^k = \mathsf{ATISP}(\log^k n, \log n). On też to pokazałNCk⊆AALTSP(logkn,logn)⊆NCk+1NCk⊆AALTSP(logk⁡n,log⁡n)⊆NCk+1\mathsf{NC}^k \subseteq …
2
Wyniki dotyczące złożoności funkcji rekurencyjnych o niższych elementach?
Zaintrygowany ciekawym pytaniem Chrisa Presseya na temat funkcji elementarno-rekurencyjnych badałem więcej i nie mogłem znaleźć odpowiedzi na to pytanie w Internecie. Te podstawowe funkcje rekurencyjne odpowiadają dobrze wykładniczemu hierarchii .DTIME (2)n) ∪ DTIME (2)2)n) ∪ ⋯DTIME(2n)∪DTIME(22n)∪⋯\text{DTIME}(2^n) \cup \text{DTIME}(2^{2^n}) \cup \cdots Z definicji wydaje się proste, że problemy decyzyjne rozstrzygalne (termin?) …
1
Literatura wokół NP vs EXPTIME
Nawet jeśli nie jest to kluczowa kwestia, nie widzę żadnej literatury wokół tego pytania. Czy są wyniki relatywizacji? Czy nie byłoby łatwo udowodnić ścisłe włączenie poprzez dostosowanie niedeterministycznego twierdzenia o hierarchii czasu poprzez badanie wszystkich możliwych ścieżek maszyny NP?
3
Interaktywne dowody za pomocą Postselection?
Zdefiniuj model obliczeniowy MPostBQP, aby był identyczny z PostBQP, z wyjątkiem tego, że dopuszczamy wielomianowo wiele pomiarów kubitowych przed pomiarem selekcyjnym i pomiarem końcowym. Czy możemy podać jakiekolwiek dowody wskazujące, że MPostBQP ma większą moc niż PostBQP? Zdefiniuj MPostBQP [k], aby umożliwić wiele rund pomiaru i wyboru po dokonaniu ostatecznego …
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.