OKPEDIA ANALISI COMPLESSITà

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.

https://www.okpedia.it/uguaglianza_classi_di_complessita_p_np




Questo sito utilizza cookie tecnici. Sono presenti alcuni cookie di terzi ( Gooogle, Facebook ) per la personalizzazione degli annunci pubblicitari. Cliccando su OK, scorrendo la pagina o proseguendo la navigazione in altra maniera acconsenti all’uso dei cookie.

Per ulteriori informazioni o per revocare il consenso fai riferimento alla Privacy del sito.