Uguaglianza classi di complessità P NP

L'uguaglianza delle classi di complessità P e NP. Secondo alcuni autori le classi di complessità P e NP si eguagliano nel caso in cui si possieda un infinito numero di processori e risorse informatiche a disposizione per la risoluzione e la verifica del problema di tipo NP. In tali casi l'insieme dei problemi di classe complessità NP potrebbe coincidere teoricamente con l'insieme dei problemi di classe di complessità P.

Critica. L'uguaglianza tra l'insieme dei problemi P e NP non è provata scientificamente ed è soggetta a diverse critiche. La maggioranza dei matematici ritiene che una infinita capacità computazionale possa contribuire ad eguagliare una parte dei problemi NP e P, tuttavia resterebbero comunque al di fuori dell'eguaglianza i problemi più estremi o più difficili della classe NP, detti problemi NP Completi, per i quali non esiste alcuna soluzione dimostrata di classe P.