complessita computazionale NP

complessita computazionale NP

complessità computazionale NP locuzione con cui si indica la complessità di calcolo di un problema di decisione (un problema cioè la cui soluzione può essere soltanto «sì» oppure «no») che è verificabile in un tempo polinomiale (correlato alla dimensione del problema): non si decide, quindi, in tempo polinomiale se una particolare istanza del problema (cioè i valori assunti dai parametri che vi compaiono) è affermativa o meno, ma si verifica un’istanza affermativa in tempo polinomiale (→ complessità computazionale).