• Il problema
• La soluzione
• Sommario

Se trascorri del tempo nella comunità di programmazione probabilmente senti il termine “P contro NP” piuttosto frequentemente. Sfortunatamente, anche molti con una formazione informatica formale hanno una debole comprensione del concetto.

Quindi ecco una spiegazione semplice e concisa:

Il problema

P vs. NP Il problema P vs. NP chiede se ogni problema la cui soluzione può essere rapidamente verificata da un computer può anche essere rapidamente risolto da un computer., (Wikipedia)

Quindi cerchiamo di capire cosa intendiamo per P e NP.

I problemi P sono facilmente risolvibili dai computer e i problemi NP non sono facilmente risolvibili, ma se si presenta una potenziale soluzione è facile verificare se è corretta o meno.

Come puoi vedere dal diagramma sopra, tutti i problemi P sono problemi NP. Cioè, se è facile per il computer risolvere, è facile verificare la soluzione. Quindi il problema P vs NP sta solo chiedendo se questi due tipi di problemi sono gli stessi, o se sono diversi, cioè che ci sono alcuni problemi che sono facilmente verificabili ma non facilmente risolvibili.,

Attualmente sembra che P NP NP, il che significa che abbiamo molti esempi di problemi a cui possiamo verificare rapidamente le potenziali risposte, ma che non possiamo risolvere rapidamente. Diamo un’occhiata ad alcuni esempi:

• Un venditore ambulante vuole visitare 100 città diverse guidando, iniziando e terminando il suo viaggio a casa. Ha una scorta limitata di benzina, quindi può guidare solo per un totale di 10.000 chilometri. Vuole sapere se può visitare tutte le città senza rimanere a corto di benzina., (da Wikipedia)
• Un agricoltore vuole portare sul mercato 100 angurie di diverse masse. Ha bisogno di imballare i cocomeri in scatole. Ogni scatola può contenere solo 20 chilogrammi senza rompersi. L’agricoltore deve sapere se 10 scatole saranno sufficienti per lei per trasportare tutti i 100 cocomeri sul mercato. (da Wikipedia)

Tutti questi problemi condividono una caratteristica comune che è la chiave per capire l’intrigo di P contro NP: per risolverli devi provare tutte le combinazioni.

La soluzione

Questo è il motivo per cui la risposta al P vs., Il problema NP è così interessante per le persone. Se qualcuno fosse in grado di dimostrare che P è uguale a NP, renderebbe difficili problemi del mondo reale banali per i computer.

Sommario

1. P vs. NP si occupa del divario tra i computer in grado di risolvere rapidamente i problemi rispetto al solo essere in grado di testare le soluzioni proposte per la correttezza.
2. In quanto tale, il problema P vs NP è la ricerca di un modo per risolvere problemi che richiedono il tentativo di milioni, miliardi o trilioni di combinazioni senza dover effettivamente provare ciascuno.,
3. Risolvere questo problema avrebbe effetti profondi sull’informatica e quindi sulla nostra società.

7 febbraio 2017 — Aggiunte le attribuzioni di Wikipedia.
2 marzo 2014-Ripulito alcune delle spiegazioni per evitare confusione.

Note