Pytania otagowane jako advice-and-nonuniformity

Przypuszcza się, że ponieważ odwrotność oznaczałaby . Twierdzenie Ladnera stwierdza, że ​​jeśli a następnie . Wydaje się jednak, że dowód nie uogólnia na więc możliwość ie wydaje się otwarty.NP⊈P/polyNP⊈P/poly\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}PH=Σ2PH=Σ2\mathsf{PH} = \Sigma_2P≠NPP≠NP\mathsf{P} \ne \mathsf{NP}NPI:=NP∖(NPC∪P)≠∅NPI:=NP∖(NPC∪P)≠∅\mathsf{NPI} := \mathsf{NP} \setminus(\mathsf{NPC} \cup \mathsf{P}) \ne \emptysetP/polyP/poly\mathsf{P}/\text{poly}NPI⊂P/polyNPI⊂P/poly\mathsf{NPI} \subset \mathsf{P}/\text{poly}NP⊂NPC∪P/polyNP⊂NPC∪P/poly\mathsf{NP} \subset \mathsf{NPC} \cup \mathsf{P}/\text{poly} Zakładając, że …

29 cc.complexity-theory  complexity-classes  advice-and-nonuniformity  p-vs-np  np-intermediate 

Karp-Lipton Theoem , że jeśli , a następnie P H zapada się Ď P 2 . W związku z tym, zakładając, że separację między Ď P 2 i Ď P 3 , nr N P -Complete Problem ten należy do P / P ° l y .N P ⊂ P …

20 cc.complexity-theory  np  conditional-results  advice-and-nonuniformity  average-case-complexity 

Język jest w języku jeśli istnieje maszyna Turinga z logami, która decyduje o języku z wielomianową ilością porad.L/polyL/polyL/poly Zobacz tutaj, aby uzyskać więcej informacji: https://en.wikipedia.org/wiki/L/poly Pytanie Jakie są konsekwencje ?P⊆L/polyP⊆L/polyP \subseteq L/poly

14 cc.complexity-theory  circuit-complexity  polynomial-time  advice-and-nonuniformity  logspace 

oznacza N P ⊆ P / P O l y , który z kolei ma wpływ interesujące jak załamania wielomianu hierarchii.P/poly=NP/polyP/poly=NP/polyP/poly = NP/polyNP⊆P/polyNP⊆P/polyNP \subseteq P/poly Czy są interesujące implikacje dla ?P/poly≠NP/polyP/poly≠NP/polyP/poly \neq NP/poly

12 cc.complexity-theory  conditional-results  advice-and-nonuniformity 

Pytanie ogólne Czy twierdzenie o hierarchii przestrzeni generalizuje się do obliczeń niejednorodnych? Oto kilka bardziej szczegółowych pytań: L/poly⊊PSPACE/polyL/poly⊊PSPACE/polyL/poly \subsetneq PSPACE/poly Czy dla wszystkich funkcji f (n) możliwych do zbudowania w przestrzeni f(n)f(n)f(n)jest DSPACE(o(f(n)))/poly⊊DSPACE(f(n))/polyDSPACE(o(f(n)))/poly⊊DSPACE(f(n))/polyDSPACE(o(f(n)))/poly \subsetneq DSPACE(f(n))/poly ? Dla jakich funkcji h(n)h(n)h(n) wiadomo, że: dla wszystkich możliwych do zbudowania przestrzeni f(n)f(n)f(n) , …

11 cc.complexity-theory  space-bounded  space-complexity  advice-and-nonuniformity  hierarchy-theorems 

Przez BPP / linear mam na myśli maszyny BPP z liniową radą, która spełnia obietnicę, gdy otrzyma „prawidłową” radę, a derandomizacja powinna dać nam, powiedzmy, algorytm P / liniowy lub (SUBEXP / liniowy). Jeśli zastosujemy niejednolite założenia, uważam, że klasyczne wyniki powinny zadziałać, ponieważ możemy „oszukać” niejednolitych przeciwników. Jednak przy …

10 cc.complexity-theory  derandomization  advice-and-nonuniformity 

Ciekawi mnie, w jaki sposób niejednorodność okazała się przydatna w obliczeniach. Jednym ze sposobów jest losowość, jak wBPP⊆P/polyBPP⊆P/polyBPP \subseteq P/poly, a kolejnym są tabele przeglądowe, które służą do pokazania, że ​​wszystkie języki mają niejednolite obwody. W szczególności interesują mnie sposoby, w jakie obiekty, o których wiadomo, że istnieją za pomocą …

9 circuit-complexity  advice-and-nonuniformity 

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 , \ …

9 cr.crypto-security  relativization  advice-and-nonuniformity  search-problem  random-oracles 

To pytanie powstało w kontekście kryptografii, ale poniżej przedstawię je w kategoriach teorii złożoności, ponieważ ludzie tutaj są bardziej zaznajomieni z tym ostatnim. To pytanie dotyczy problemów w NP, ale nie w średniej P / poli i pokonania premii przez Oracle Access . Nieformalne oświadczenie: kiedy nierównomiernym przeciwnikom (tj. Wielorakiej …

9 cc.complexity-theory  cr.crypto-security  np  advice-and-nonuniformity  average-case-complexity