Pytania otagowane jako oracles

Pytania dotyczące maszyn wyroczni w teorii złożoności obliczeniowej. Wyrocznie mogą służyć jako wskaźnik, że oddzielenie klas złożoności wykracza poza zakres niektórych technik dowodowych.

2
Czy
Przez http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf Jeśli jest językiem PSPACE uzupełniania, P = N P A .AAAPA=NPAPA=NPAP^{A}=NP^{A} Jeśli jest deterministyczną wyrocznią wielomianową, P B ≠ N P B (przy założeniu P ≠ N P ).BBBPB≠NPBPB≠NPBP^{B}\ne NP^{B}P≠NPP≠NPP\ne NP to klasa problemów decyzyjnych analogiczna dla # P i P ⊆ P P ⊆ P S P …
1
Relatywizowany świat, w którym
Chciałabym wiedzieć, czy istnieje zrelatywizowane świat, w którym . Jestem również zainteresowany, aby wiedzieć, czy istnieje zrelatywizowane świat, w którym P B ≠ N P B = P P B .P.ZA= N P.ZA≠ P PZAPA=NPA≠PPA{\bf P^A}={\bf NP^A}\not = {\bf PP^A}P.b≠ N P.b= P PbPB≠NPB=PPB{\bf P^B} \not = {\bf NP^B} = …
1
Mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa
W artykule na temat relatywizacji obliczeń przestrzeni logicznej Ladner i Lynch konstruują wyrocznię, do której . W literaturze można znaleźć więcej patologicznych przykładów. Czytałem kilka artykułów na temat relatywizowanych małych klas kosmicznych, a jednym z podstawowych narzędzi w tym obszarze jest mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa (RST), który wymaga deterministycznej, …
2
Czy wyroki są stowarzyszone?
To pytanie może mieć oczywistą odpowiedź ... ale oto i tak pytanie. Intuicyjnie jest to następujące prawdopodobne stwierdzenie - „maszyna z podprogramem A, który z kolei ma podprogram B, jest tym samym, co maszyna z podprogramem A, który ma dostęp do podprogramu B”. Aby formalnie zdefiniować ten problem, użyję niekonwencjonalnej …
1
Czy w teorii typów istnieje dobre pojęcie o braku terminacji i zatrzymaniu dowodów?
Konstruktywna teoria typów z jej podstawową interpretacją w ramach korespondencji curry-howard składa się wyłącznie z całkowitych, obliczalnych funkcji. W literaturze niektórzy mówili o stosowaniu „teorii typów obliczeniowych” w celu przedstawienia nieterminacji w programach funkcjonalnych, ale w artykułach, na które się natknąłem, nie wydaje się to być główną motywacją dla teorii …
1
Czy
W literaturze nie znalazłem stwierdzenia dotyczącego i ; wskazówki będą mile widziane.N P R PMAMA\mathsf{MA}NPRPNPRP\mathsf{NP}^\mathsf{RP} Wierzę, że są równi: N P R PMA⊆NPRPMA⊆NPRP\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP} : Maszyna zgaduje ciąg Merlina, a wyrocznia weryfikuje ciąg tak, jak Arthur.NPNP\mathsf{NP}RPRP\mathsf{RP} NPRP⊆MANPRP⊆MA\mathsf{NP}^\mathsf{RP} \subseteq \mathsf{MA} : Merlin zgaduje obliczenia akceptujące maszyny , w tym wszystkie …
4
Wyniki Oracle dla P vs BPP
Niech będzie dowolnym EXP kompletnym problemem. Następnie .P A = N P AZAAAP.ZA= NP.ZAPA=NPAP^A = NP^A Niech będzie jakiś wyrocznią, która bierze pod rachunkach zapytań (a TM w P) uczynią, a my możemy dostać .M P B ≠ N P BbBBM.MMP.b≠ N.P.bPB≠NPBP^B \neq NP^B Pytanie: Czy mamy podobne wyniki wyroczni …
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.