Warunki wystarczające do upadku hierarchii wielomianowej (PH)

Jakie są niektóre (mało znane) twierdzenia, że ​​jeśli prawda, PH musi się załamać?

Docenia się odpowiedzi zawierające krótkie stwierdzenie wysokiego poziomu z referencjami. Próbowałem przeszukać wstecz bez większego szczęścia.

Istnieje (rosnąca) liczba sparametryzowanych wyników złożoności, w których istnienie wielomianowego jądra oznacza załamanie PH do trzeciego poziomu. Technika centralna jest podana w [1], w oparciu o wcześniejsze prace (wymienione w [1]).

Jako prosty przykład problem -Path jest sparametryzowaną wersją problemu Najdłuższej ścieżki:$k$

-Path$k$
Instance: Wykres i liczba całkowita k . Parametr: k . Pytanie: Czy G zawiera ścieżkę o długości k ?$G$$k$
$k$
$G$$k$

Problem ten występuje w FPT (z nieco praktycznymi algorytmami), ale w [2] pokazują, że jeśli ma jądro wielomianowe (w ), wówczas PH zapada się do Σ P 3 . (Obecna prezentacja jest zwykle wyrażana jako ujemny wynik kernalizacji, chyba że NP ⊆ coNP / poly lub coNP ⊆ NP / poly, więc szukając czegoś takiego jak „brak wielomianowego jądra, chyba że” uzyska wiele wyników).$k$$\Sigma^{P}_{3}$$\subseteq$$\subseteq$

Bibliografia

1. HL Bodlaender, BMP Jansen i S. Kratsch, „Kernelizacja dolnych granic przez skład krzyżowy”, SIAM J. Discrete Math., 28 (2014), s. 277–305. [wersja arXiv]
2. HL Bodlaender, RG Downey, MR Fellows, D. Hermelin, „O problemach bez jąder wielomianowych”, Journal of Computer and System Sciences, 75 (8): 423-434. 2009. [Wersja hostowana Stanford]

$\Sigma_{3}^{P}$

Kolejnym interesującym warunkiem jest to:

$\#3SAT$$BPP^{NP}$$BPP$$\Sigma_2^{P}$$\#3SAT$$\Sigma_3^{P}$

$PH \subseteq P^{\#P}$

$\#3SAT$$\#3SAT$

Bibliografia:

[1] Jim Kadin, Wielomianowa hierarchia czasu załamuje się, jeśli załamie się hierarchia boolowska , SIAM Journal on Computing 17 (1988), no. 6, s. 1263–1282, doi: 10.1137 / 0217080 .

[2] Richard Chang i Jim Kadin, Hierarchia boolowska i hierarchia wielomianowa: bliższe połączenie , SIAM Journal on Computing 25 (1996), no. 2, s. 340–354, doi: 10.1137 / S0097539790178069 .

$\mathsf{NP}$$\mathsf{PH}$$\mathsf{NP}=\mathsf{UP}$$\mathsf{PH}$

$L \in \mathsf{NP}$$\varphi$$\varphi$$x$$(\varphi,x) \in L$$\varphi$ $x$$(\varphi,x) \in L$$\mathsf{PH}$

Kolejna formalizacja to:

$\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$$\mathsf{PH}$

$A := \forall i , \Sigma^{P}_{i} \neq \Pi^{P}_{i}$$\mathbb{PH}$$A \implies B$

$\bar{B} \implies \bar{A}$$\mathbb{PH}$

1. $\mathbb{PH}$
2. $\mathbb{PH}$

$\mathbb{PH}$

Oto kilka zwięzłych:

1. $PSPACE \subseteq P/poly$
2. $EXP \subseteq P/poly$
3. $NP \subseteq P/log$