Czy NP jest w ?

$DTIME(n^{polylogn})$ jest znany jako $QP$ (quasi-wielomian).

$NP\not \subset QP$ $P\neq NP$

Niektóre typowe przypuszczenia, takie jak hipoteza wykładniczego czasu, sugerują . $NP\not \subset QP$

— RB
źródło

Mówisz, że „Niektóre typowe przypuszczenia ...”. Jakie są inne oprócz ETH? Jestem bardzo zainteresowany, ponieważ obecnie pracuję nad powiązaniem NP i QP - przynajmniej mam taką nadzieję ...

— Matt Groff

Innym dobrym powodem, aby sądzić, że jest to, że implikuje , a ten drugi jest uważany za bardzo mało prawdopodobny. Tę implikację można udowodnić za pomocą argumentu wypełniającego, patrz np. W dowodzie Twierdzenia 2 w następującym dokumencie: $NP\not\subseteq QP$ $NP\subseteq QP$ $EXP=NEXP$

H. Buhrman i S. Homer, „Obwody wielobiegunowe, prawie rzadkie wyrocznie i hierarchia wykładnicza”, Podstawy technologii oprogramowania i informatyki teoretycznej, Springer LNCS obj. 652, 1992, s. 116–127, pdf

— Andras Farago
źródło

Bardzo podoba mi się ta odpowiedź. Biorąc pod uwagę odpowiedź na RB, to sprawia, że zastanawiam się, co, jeśli w ogóle, jest relacja między ETH i założeniu

E X P \neq N E X P

$\mathsf{EXP} \neq \mathsf{NEXP}$

— Joshua Grochow

@Joshua Nie przeszukiwałem literatury na ten temat, ale myślę, że każde naruszenie ETH prawdopodobnie oznacza pewne załamanie na wyższym poziomie. Sądzę, że poziom zależy od „jak silnego” naruszenia ETH, silniejsze naruszenia skutkują bardziej dramatycznymi upadkami. Jak wskazano w odpowiedzi silne naruszenie ETH z

oznacza

. Jeśli weźmiemy łagodniejsze naruszenie, na przykład zakładając, że

jest w klasie podwykonawczej większej niż

, wówczas załamanie jest prawdopodobnie przesunięte w górę (np. Do podwójnej klasy wykładniczej lub nawet wyższej).

N P \subseteq Q P

$NP\subseteq QP$

E X P = N E X P

$EXP=NEXP$

N P

$NP$

Q P

$QP$

— Andras Farago

Thansk, ale prosi o bezpośrednim pośrednio obu kierunkach między ETH i

. Mamy teraz dwie odpowiedzi - ETH oznacza

oznacza

- i byłem ciekawy, czy jedna była konsekwencją drugiej.

E X P \neq N E X P

$\mathsf{EXP} \neq \mathsf{NEXP}$

N P ⊈ Q P

$\mathsf{NP} \not\subseteq \mathsf{QP}$

N E X P \neq E X P

$\mathsf{NEXP} \neq \mathsf{EXP}$

N P ⊈ Q P

$\mathsf{NP} \not\subseteq \mathsf{QP}$

— Joshua Grochow

Niestety nie jestem świadomy bezpośredniej implikacji. Inna uwaga jest dość interesująca, że naruszenia ETH mogą powodować nie tylko załamania, ale także separacje, jeśli chodzi o dolne granice obwodu. Artykuł Ryana Williamsa (pdf) dowodzi, że nawet najmniejsze naruszenie ETH oznaczałoby pewną notorycznie trudną do udowodnienia dolną granicę obwodu.

— Andras Farago