Czy

Przez http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf

Jeśli jest językiem PSPACE uzupełniania, . $A$ $P^{A}=NP^{A}$

Jeśli jest deterministyczną wyrocznią wielomianową, (przy założeniu ). $B$ $P^{B}\ne NP^{B}$ $P\ne NP$

to klasa problemów decyzyjnych analogiczna dla i , $PP$ $\#P$ $P\subseteq PP\subseteq PSPACE$

ale ani ani jest znane. Ale czy to prawda? $P=PP$ $PP=PSAPCE$

? $coNP^{\#P}=NP^{\#P}=P^{\#P}$

cc.complexity-theory complexity-classes counting-complexity open-problem oracles Mike Chen
źródło

Jeśli

jest deterministyczny czasie wielomianowym oracle Chyba masz na myśli mamy wierzyć

. (ponieważ

)

B

$B$

P^{B} \neq N P^{B}

$P^B \neq NP^B$

P^{B} = P

$P^B = P$

N P^{B} = N P

$NP^B = NP$

Ramprasad

Mogę się mylić, ale pozwól, że spróbuję: Twoje pierwsze pytanie zakłada, że drugie zabezpieczenie nie jest ścisłe. Innymi słowy, zakłada, że PP = PSPACE. W takim przypadku myślę, że równość utrzymuje wynik wymieniony na początku. Czy mam rację? (PS: Odwrotna

sytuacja

Twierdzenie Tody może być tutaj istotne, ponieważ wskazuje, że można by złożyć różnicę między

do wyroczni

. (Ale nie jestem tego w 100% pewien).

P

$P$

N P

$NP$

#P

$#P$

Boaz Barak

Odpowiedź na twoje czwarte pytanie brzmi: tak. Nawet NP ^ PSPACE jest zawarty w PSPACE, więc na pewno NP z wyrocznią #P jest w PSPACE.

Robin Kothari,

Jak sugerują komentarze, niektóre z pytań zawartych w tym poście (i niektóre ostatnio dodane pytania) są podstawowe. Pokaż dowody, że naprawdę cię to obchodzi. Zobacz także meta.cstheory.stackexchange.com/questions/300/… , meta.cstheory.stackexchange.com/questions/300/… .

Tsuyoshi Ito,

Odpowiedzi:

Jest to otwarty problem w teorii złożoności przez wiele lat, jeśli zawali się, gdzie jest wielomianową hierarchią czasu. Jest również otwarty problem skonstruowania wyrocznię oddzielenia z . $\mathsf{PH}^{\mathsf{\#P}}$ $\mathsf{PH}$ $\mathsf{P}^{\mathsf{\#P}}$ $\mathsf{PSPACE}$

Bin Fu
źródło

Witamy w CSTheory.SE, @Bin Fu! :)

Daniel Apon

A może już tu byłeś, ale i tak witaj! ;)

Daniel Apon

Dzięki, Daniel Apon. Wiadomo, że PH ^ {Parity P} załamuje się. To będzie bardzo interesujące, jeśli można udowodnić, że PH ^ {# P} załamuje się.

Bin Fu

Ciekawe, czy mógłbyś podać odniesienie do

i problem jego załamania, proszę?

P H^{# P}

$PH^{\#P}$

neofita

Przez http://portal.acm.org/citation.cfm?id=116858

Jeśli nie będę tego źle interpretować. Twierdzenie 4,1 (ii) z napisem " " a . $NP^{\mathbf{C}K}=\exists \mathbf{C}K$ $coNP^{\mathbf{C}K}=\forall\mathbf{C}K$

Lemat 3.4 (c) mówi: „Dla dowolnego w hierarchii liczenia ”. $K$ $\exists K\cup\forall K\subseteq\mathbf{C}K\subseteq\exists\mathbf{C}K\cap\forall\mathbf{C}K$

Wymiana przez , otrzymujemy . $K$ $P$ $PP\subseteq\exists PP\cap\forall PP$

Co oznacza, że . $P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$

A utrzymuje, czy hierarchia wielomianowa się zawali, a hierarchia zliczania upadnie. $P^{\#P}=NP^{\#P}=coNP^{\#P}$

Mike Chen
źródło

Włączenie P ^ X ⊆ NP ^ X ∩ coNP ^ X dla dowolnej klasy X wynika z definicji i do tego nie potrzebujesz Twierdzenia 4.1 Torana. Nie rozumiem, dlaczego załamanie hierarchii wielomianowej i hierarchii zliczania implikuje P ^ # P = NP ^ # P = coNP ^ # P. Czy możesz rozwinąć?

Tsuyoshi Ito,

@Tsuyoshi: Jeśli zapada wielomianowe hierarchii

, a następnie

. Jeśli hierarchia zliczania zwija, a następnie

, to znaczy

. Według lematu 3.4 (c),

, więc

P = N P = c o N P

$P=NP=coNP$

P^{# P} = N P^{# P} = c o N P^{# P}

$P^{\#P}=NP^{\#P}=coNP^{\#P}$

C C P = C P

$\mathbf{C}\mathbf{C}P=\mathbf{C}P$

P P^{P P} = P P

$PP^{PP}=PP$

\exists K \cup \forall K \subseteq C K

$\exists K\cup\forall K\subseteq\mathbf{C}K$

, czyli

tego wzoru powinny być

zamian.

P^{# P} \subseteq N P^{# P} \cap c o N P^{# P}

$P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$

\subseteq N P^{# P} \cup c o N P^{# P} \subseteq P P^{P P}

$\subseteq NP^{\#P}\cup coNP^{\#P}\subseteq PP^{PP}$

= P P = P^{# P}

$=PP=P^{\#P}$

\subseteq

$\subseteq$

=

$=$

Mike Chen,

„Upadek hierarchii wielomianowej” niekoniecznie oznacza P = NP, a „zapadnięcie się hierarchii liczenia” niekoniecznie oznacza PP = PP ^ PP.

Tsuyoshi Ito,

Ponadto P = NP nie implikuje P ^ # P = NP ^ # P, o ile wiem (ale może czegoś mi brakuje).

Tsuyoshi Ito,

Częstym błędem w tego rodzaju argumentach jest założenie, że relatywizacja do wyroczni jest operacją na zbiorze języków, ale zamiast tego jest operacją typu obliczeniowego, co drastycznie wpływa na to, jakie języki są w klasie.

Derrick Stolee