Pytania otagowane jako relativization

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, …
4
Czy diagonalizacja oddaje istotę separacji klasowej?
Nie pamiętam, że widziałem separację klas nieopartą na wynikach diagonalizacji i relatywizacji. Diagonalizacja może być nadal używana do oddzielania pozostałych znanych klas, ponieważ argumenty nierelatywizujące mogą być nadal stosowane w konkluzji o diagonalizacji lub w konstrukcji diagonalizowanej maszyny Turinga. Oto kilka powiązanych pytań: Czy istnieją dowody separacji klas nieoparte na …
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 …
1
Czy losowa wyrocznia może zmienić, które problemy TFNP są średnio trudne?
Zastanawiałem się nad następującym pytaniem w różnych momentach, odkąd widziałem to pytanie w kryptografii . Pytanie Pozwolić RRRbyć relacją TFNP . Czy losowa wyrocznia może pomóc P / poli w przełamaniu z nieistotnym prawdopodobieństwem? Bardziej formalnie, RRR \newcommand{\Pr}{\operatorname{Pr}} \newcommand{\E}{\operatorname{\mathbb{E}}} \newcommand{\O}{\mathcal{O}} \newcommand{\Good}{\mathsf{Good}} Robi dla wszystkich algorytmów P / poli , \ …
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.