La relazione esatta tra classi di complessità e le complessità dell'algoritmo [duplicato]

Question

Questa domanda ha già una risposta qui:

• Qual è la definizione di P, NP, NP -Complete e NP-hard? 7 risposte

Sono tutti gli algoritmi che hanno polinomiale complessità temporale appartengono alla classe P? E di classe P non hanno alcun algoritmo che ha complessità non polinomiale?

Sono tutti gli algoritmi che hanno complessità non polinomiale appartengono a NP o NP-Hard o entrambi?

Sto solo cercando di capire il rapporto di base.

Answer 1

$ P $ è definita come la classe dei problemi (decisione) che hanno un algoritmo che li risolve in tempo polinomiale (in una TM, o un modello polinomialmente equivalente). Così, $ P $ contiene esattamente questi problemi, né più né meno.

Per quanto riguarda $ NP $ - la situazione è più delicata. Un problema è in NP $ $ se ha un algoritmo non deterministico che viene eseguito in tempo polinomiale. Una, più user-friendly definizione equivalente, è che data una soluzione al problema, è possibile verificare che di correttezza in tempo polinomiale nella dimensione del problema. Ad esempio, in un grafico e un percorso che sostiene di essere un hamiltoniana, è possibile verificare in tempo polinomiale che è effettivamente un percorso hamiltoniano. Quindi, il problema di decidere se un grafico ha un percorso hamiltoniano è in $ NP $.

Chiarimento: $ NP $ è una classe di problemi , non di algoritmi . Un algoritmo non appartiene a $ NP $.

Ora, alcuni problemi sono noti per non avere un algoritmo di tempo polinomiale. Questo non significa che essi sono in $ NP $. In effetti, alcuni problemi sono noti per non essere in $ NP $. Per esempio, qualsiasi $ NEXP $ problema -Hard.

Per quanto riguarda $ NP $ problemi -duro - dal momento che non sappiamo se $ P = NP $ o no, non sappiamo se ogni problema al di fuori $ P $ è $ NP $ -Hard. Se $ NP = P $, allora ogni problema è $ NP $ -Hard (ad eccezione di $ \ Sigma ^ * $ e $ \ emptyset $).

Questa risposta (che è di gran lunga incompleta) si estende per circa 3 settimane di materiale in un corso base di complessità. Forse prendere in considerazione accuratamente la lettura di un libro di testo, come ad esempio Sipser di "teoria della computazione".

Answer 2

Tutti gli algoritmi che risolvono qualche problema decisionale nel mondo dello spettacolo tempo polinomiale che i loro problemi sono in $ P $. Ma ci sono certamente gli algoritmi che non prendono tempo polinomiale per i problemi in $ P $. Si potrebbe ordina per la generazione di tutti i $ n! Permutazioni $ dell'ingresso, e controllare ogni se è ordinato. Questo algoritmo vuole un tempo più che esponenziale, ma il problema ha una soluzione in tempo polinomiale.