Czy różni się od ?

Czy możemy udowodnić, że dla każdego języka który nie jest -hard (zakłada to ), ? Alternatywnie, czy można to udowodnić przy jakichkolwiek uzasadnionych założeniach? $L\in\mathsf{NP}$ $\mathsf{NP}$ $\mathsf P \ne \mathsf{NP}$ $\mathsf{P}^L \ne \mathsf{P}^{\text{SAT}}$

cc.complexity-theory complexity-classes np-intermediate GMB
źródło

Myślę, że to pytanie ma głupią odpowiedź: pozwól , a potem na pewno kiedy przyjmiesz, że . Możesz więc chcieć, nadal zakładając, że , będzie w a nie -hard. [Edytuj: Och, przeczytałem twój komentarz poniżej, więc twoje pytanie wydaje się brzmiać: „Czy to prawda, że dla wszystkich takich nierówność występuje?”, A nie „Czy istnieje takie ?” => Edytuję twoje pytanie!]

L \in P \subseteq N P

$L\in\mathsf P\subseteq\mathsf{NP}$

P^{L} \neq P^{SAT}

$\mathsf P^L\neq \mathsf P^{\text{SAT}}$

P \neq N P

$\mathsf P\neq\mathsf{NP}$

P \neq N P

$\mathsf P\neq\mathsf{NP}$

L

$L$

N P ∖ P

$\mathsf{NP}\setminus\mathsf P$

N P

$\mathsf{NP}$

L

$L$

L

$L$

Bruno

Odpowiedzi:

Zależy od twojej definicji NPI. Jeżeli A jest niekompletne dla redukcji Turinga, odpowiedź brzmi tak ponieważ SAT nie jest w . $P^A$

Jeśli A jest po prostu niekompletny, to nie wiemy, jak to udowodnić. Mamy relatywizowany świat z zestawem A w NP takim, że A nie jest NP-kompletny poprzez redukcje wielokrotne jeden, ale SAT można obliczyć za pomocą pojedynczego zapytania do A. (Twierdzenie 1.9 w tym artykule ).

Lance Fortnow
źródło

Masz na myśli Twierdzenie 1.9?

Geoffrey Irving

Masz rację. Naprawiony.

Lance Fortnow