Can NP-Intermediate esiste se P = NP?

Question

La mia comprensione è che il teorema di Ladner è fondamentalmente questo:

  

P! = NP implica che esiste un NPI set dove NPI non è in P e   NPI non è NP-completo

Cosa succede a questo teorema, se assumiamo che P = NP, piuttosto che P! = NP? Sappiamo che se NP intermedio non esiste, allora P = NP. Ma può NP Intermedio esistere se P = NP?

Answer 1

NPI deve implica che sia in NP, ma che non è NP-completo.

Se P = NP, quindi tutti i problemi in P e NP sarà NP-completo, perché ogni problema sarà riducibile ad un altro in tempo polinomiale (∅ e Σ * non può essere NP-completo, perché non possiamo mappare un problema di arbitrario a una di loro - non avremo nulla da mappare per il caso positivo / negativo, tuttavia, dal momento che sono in P, non si cura di loro per lo scopo di questa domanda)

Dal momento che tutti i problemi in NP sono NP-completo, NPI non può esistere.

Answer 2

È mancato una proprietà di NPI: Ogni elemento di NPI è in NP (ma non in P). Questo è chiaramente impossibile se P = NP, quindi se P = NP, NPI deve essere vuota.

Answer 3

Se P = NP, allora NPI non può esistere supponendo che è un sottoinsieme di NP, come tutti NP è in P e quindi la parte "non P" della definizione di NPI non avrebbe retto per qualsiasi problema. Così la classe NPI sarebbe vuoto in quel caso.

Answer 4

Il teorema di Ladner nella sua formulazione classica non fa nulla di stato in merito al caso in cui P = NP.

Da logica di base, $ A \ rightarrow B $ non fa niente stato di circa $ non (A) $ ... purtroppo.

Inoltre, se $ P = NP $ e $ NP $ è Cook-riducibile a $ NP-completo $ ... allora vorrebbe dire che la maggior parte dei problemi che calcoliamo in calcolo (addizione, trasformate di Fourier, di smistamento) sono riducibili a, diciamo, somma sottoinsieme .... supponendo che il teorema di Cook è valido. Questo sarebbe abbastanza spremere le meningi.

Ma dal teorema di Ladner, abbiamo appena posso dire nulla in merito al caso $ P = NP $.