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.
Zdefiniuj ioioio - jako klasę języków taką, że istnieje język i dla nieskończenie wielu , i zgadzają się we wszystkich przypadkach długości n . (To jest klasa języków, które można „rozwiązywać nieskończenie często, w podwykonawczym czasie”).SUBEXPSUBEXPSUBEXPL ′ ∈ ∩ ε >...
W wielu domenach istnieją techniki kanoniczne, które każdy specjalista w tej dziedzinie powinien opanować. Na przykład, w przypadku redukcji przestrzeni logicznej, „sztuczka bitowa” dla kompozycji polega na tym, że nie konstruuje się pełnego wyniku złożonej funkcji, ale zawsze prosi o ponowne...
Zasadniczo taśma zapytania dla wyroczni liczy się do złożoności przestrzennej bazy TM. Wydaje się jednak prawdopodobne, aby zezwolić na taśmę Oracle tylko do zapisu (na przykład w przypadku redukcji przestrzeni L). Czy taka konstrukcja jest przydatna? Czy przynosi jakieś absurdalne...
Cóż, tytuł prawie wszystko mówi. Interesujące pytanie powyżej zostało zadane przez komentatora Jaya na moim blogu (patrz tutaj i tutaj ). Zgaduję, że odpowiedź brzmi „tak” i że istnieje stosunkowo prosty dowód, ale nie widziałem go od razu. (Jednak z grubsza można by próbować pokazać, że jeśli...
Załóżmy, że jest drzewem o stałym stopniu, którego struktury nie znamy. Problem polega na wyprowadzeniu drzewa T przez zadawanie zapytań o postać: „Czy węzeł x leży na ścieżce od węzła a do węzła b ?”. Załóżmy, że na każde zapytanie można odpowiedzieć w stałym czasie przez wyrocznię. Znamy wartość...
Właśnie przeczytałem pytanie „ Czy rozkład liczb całkowitych jest problemem NP-zupełnym? ” ... więc postanowiłem poświęcić trochę mojej reputacji :-) zadając kolejne pytanie mając :QQQP(Q is trivial)≈1P(Q is trivial)≈1P(\text{Q is trivial}) \approx 1 Jeśli jest wyrocznią, która rozwiązuje...
tło Wiadomo, że istnieje oracle tak, że .P S P A C E A ≠ P H AAAAPSPACEA≠PHAPSPACEA≠PHAPSPACE^A \neq PH^A Wiadomo nawet, że separacja dotyczy przypadkowej wyroczni. Nieformalnie można to interpretować w ten sposób, że istnieje wiele wyroczni, dla których i są osobne.P...
W „Obliczeniach kwantowych i informacjach kwantowych” Mike'a i Ike'a algorytm Grovera został szczegółowo wyjaśniony. Jednak w książce i we wszystkich wyjaśnieniach, które znalazłem w Internecie dla algorytmu Grovera, wydaje się, że nie ma wzmianki o tym, jak zbudowana jest Wyrocznia Grovera, chyba...
Najczęstszy sposób, w jaki wyrocznie występują w teorii złożoności, jest następujący: Stała wyrocznia jest udostępniana, powiedzmy, maszynie Turinga z pewnymi ograniczonymi zasobami, i jedna bada, w jaki sposób wyrocznia zwiększa moc obliczeniową maszyny. Istnieje jednak inny sposób, w jaki...
W artykule zatytułowanym „On Deniability in Common Reference String and Random Oracle Model” Rafael Pass pisze: Zauważamy, że udowadniając bezpieczeństwo zgodnie ze standardową definicją zerowej wiedzy w modelu RO [Random Oracle], symulator ma dwie zalety w stosunku do zwykłego symulatora...
Mówiąc wprost: jaka jest zgodność między maszynami Turinga z wyroczniami a rodzinami jednorodnych obwodów z wyroczniami? Jak te ostatnie są zdefiniowane w celu uzyskania tego samego modelu obliczeniowego dla danej maszyny Turinga z Oracle? To może być elementarne pytanie, ale nie jest oczywiste,...
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...
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...
Wiadomo, że problem zatrzymania jest niemożliwy do obliczenia. Możliwe jest jednak wykładnicze „kompresowanie” informacji o problemie zatrzymania, tak aby dekompresowanie było możliwe do obliczenia. Dokładniej, można obliczyć na podstawie opisu maszyn Turinga, a n- bitowa porada stanowi odpowiedź...
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...
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...
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}...
Niewrażliwe generatory są zdefiniowane następująco: Niech będzie relacją NP, a M będzie maszyną, która akceptuje L ( R ) . Nieformalnie program jest niewrażliwym generatorem, jeśli na wejściu 1 n wytwarza pary instancji-świadka ( x , w ) ∈ R , z | x | = n , zgodnie z rozkładem, zgodnie z którym...
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...
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,...