Pytania otagowane jako relativization

1
Więcej na temat PH w PP?
Ostatnie pytanie za pytaniem, czy Huck Bennett PH klasa została zawarta w PP klasy, otrzymał nieco sprzecznych odpowiedzi (wszystko prawda, wydaje się). Z jednej strony podano przeciwnie kilka wyników wyroczni, z drugiej Scott zasugerował, że odpowiedź jest prawdopodobnie pozytywna, ponieważ twierdzenie Tody pokazuje, że PH jest w BP.PP, wariancie probabilistycznym …
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
Czy istnieje wynik w teorii obliczalności, która nie jest relatywizowana?
Czytałem artykuł Andreja Bauera Pierwsze kroki w teorii obliczeń syntetycznych . Na zakończenie zauważa to Nasza aksjatyzacja ma swoje granice: nie może udowodnić żadnych wyników w teorii obliczeń, które nie relatywizują się do obliczeń wyroczni. Jest tak, ponieważ teorię można interpretować jako wariant efektywnego toposu zbudowanego z częściowych funkcji rekurencyjnych …
1
Jaki jest „prawdziwy” powód, dla którego IP = PSPACE nie powoduje relatywizacji?
OOOcoNPO⊈IPOcoNPO⊈IPO{\sf coNP}^O \not\subseteq {\sf IP}^OcoNPO⊆PSPACEOcoNPO⊆PSPACEO{\sf coNP}^O \subseteq {\sf PSPACE}^OOOO Jednak widziałem tylko kilka osób, które wyjaśniają „bezpośrednio”, dlaczego wynik nie jest relatywizowany, a typową odpowiedzią jest „arytmetyzacja”. Po sprawdzeniu dowodu IP = PSPACE ta odpowiedź nie jest fałszywa , ale nie jest dla mnie zadowalająca. Wydaje się, że „prawdziwy” powód …
5
Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane z faktem, że nie można sprawdzić, czy dwie …
18 computability  computing-over-reals  lambda-calculus  graph-theory  co.combinatorics  cc.complexity-theory  reference-request  graph-theory  proofs  np-complete  cc.complexity-theory  machine-learning  boolean-functions  combinatory-logic  boolean-formulas  reference-request  approximation-algorithms  optimization  cc.complexity-theory  co.combinatorics  permutations  cc.complexity-theory  cc.complexity-theory  ai.artificial-intel  p-vs-np  relativization  co.combinatorics  permutations  ds.algorithms  algebra  automata-theory  dfa  lo.logic  temporal-logic  linear-temporal-logic  circuit-complexity  lower-bounds  permanent  arithmetic-circuits  determinant  dc.parallel-comp  asymptotics  ds.algorithms  graph-theory  planar-graphs  physics  max-flow  max-flow-min-cut  fl.formal-languages  automata-theory  finite-model-theory  dfa  language-design  soft-question  machine-learning  linear-algebra  db.databases  arithmetic-circuits  ds.algorithms  machine-learning  ds.data-structures  tree  soft-question  security  project-topic  approximation-algorithms  linear-programming  primal-dual  reference-request  graph-theory  graph-algorithms  cr.crypto-security  quantum-computing  gr.group-theory  graph-theory  time-complexity  lower-bounds  matrices  sorting  asymptotics  approximation-algorithms  linear-algebra  matrices  max-cut  graph-theory  graph-algorithms  time-complexity  circuit-complexity  regular-language  graph-algorithms  approximation-algorithms  set-cover  clique  graph-theory  graph-algorithms  approximation-algorithms  clustering  partition-problem  time-complexity  turing-machines  term-rewriting-systems  cc.complexity-theory  time-complexity  nondeterminism 
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, …
1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
1
Czy dowody, że permanent nie jest w mundurze
Jest to kontynuacja tego pytania i jest związana z tym pytaniem Shivy Kinali. Wydaje się, że dowody w tych dokumentach ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) używają twierdzeń hierarchicznych. Chcę wiedzieć, czy dowody są „ czystymi ” twierdzeniami o diagonalizacji, czy też używają czegoś więcej niż zwykła diagonalizacja. Więc …
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 …
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} = …
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.