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 istnieje taka wyrocznia, że ​​SAT nie jest nieskończenie często w czasie sub wykładniczym?
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 ′ ∈ ∩ ε > 0LLLL′∈∩ε>0TIME(2nε)L′∈∩ε>0TIME(2nε)L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})nnnLLLL′L′L'nnn Czy istnieje wyrocznia …
1
Czy istnieją kanoniczne techniki nierelatywizujące?
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 obliczenie wyniku dla każdego bitu wyjściowego, co pozwala zachować …
3
kosmiczne bazy TM i wyrocznie
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 wyniki?
5
P z wyrocznią z faktoryzacji liczb całkowitych
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 faktoryzacji liczb całkowitych, co jest moc P A ? AAAPAPAP^A Myślę, że …
1
Jaka jest wyrocznia o minimalnej złożoności, która oddziela PSPACE od hierarchii wielomianowej?
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 HPSPACEPSPACEPSPACEPHPHPH Pytanie Jak skomplikowane są te wyrocznie, …
3
Teoria złożoności, gdy wyrocznia jest częścią danych wejściowych
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 czasami zdarzają się wyrocznie: jako część danych wejściowych . Załóżmy na …
2
Wyczerpujący symulator protokołów zerowej wiedzy w losowym modelu Oracle
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 modelu, a mianowicie: Symulator może zobaczyć, na jakich wartościach strony …
1
Kompresowanie informacji o problemie zatrzymania w maszynach wyroczni Turinga
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ź na problem zatrzymania dla wszystkich 2 n - 1 maszyn Turinga, przy …
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)?
1
Wyrocznia, względem której
Zoologia złożoności autorstwa Grega Kuperberga stwierdza, że ​​istnieje język XXX taki, że BPPX⊈Δ2PXBPPX⊈Δ2PX\mathsf{BPP}^X \nsubseteq \mathsf{\Delta_2 \mathsf{P}}^X - innymi słowy, BPPX⊈PNPXBPPX⊈PNPX\mathsf{BPP}^X \nsubseteq \mathsf{P}^{\mathsf{NP}^X} - ale nie podaje odniesienia do tego wyniku. Dlaczego tak się dzieje? Lub gdzie można znaleźć dowód? To pytanie jest częściowo uzasadnione moją odpowiedzią na pytanie „Co wiadomo …
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.