Forum libero

Scritto da:
> che noia che barba!
>
> Pedoneria, legittima difesa e poi c'è P != NP. Non ho capito perché se un algoritmo che cerca una soluzione non è polinomiale si dà per scontato che la verifica della soluzione lo sia.

Infatti non si dà per scontato che lo sia, al contrario: si crede che esistano problemi per i quali trovare la soluzione è esponenziale ma verificarla polinomiale.

Questi problemi rientrano nella categoria NP. È una definizione e quindi vengono messi nella categoria per definizione, punto e fine.

Se però qualcuno riuscisse a dimostrare che nel caso in cui un problema può essere verificato in maniera polinomiale allora può essere sicuramente risolto anche in maniera polinomiale, allora seguirebbe che P = NP, e quindi la categorizzazione non avrebbe più senso... si crede comunque che questo non sia il caso.