01010001....Hello World....00111101

Non si può parlare di informatica senza prima aver preso in cosiderazione questo documento: Hello World! - una raccolta di programmi, in praticamente tutti i linguaggi di programmazione che esistono, che stampano l'ormai famossima frase!

Che dire del problema che affligge gli Informatici di mezzo mondo??
P?NP

P = classe di problemi che possono essere risolti in tempo polinomiale.

NP = problemi polinomiali non deterministici. Un problema è in questa classe se c'è qualche algoritmo che può indovinare una soluzione (GUESS) e verificare dove il guess è corretto in tempo polinomiale (VERIFY). Se dispongo di tanti processori (in modo da provare tutti lo stesso guess allo stesso tempo) oppure sono fortunato e dimostro sempre che il guess è corretto la prima volta, i problemi NP diventano P.

Il problema più grosso nell'informatica è quando la classe NP è equivalente alla classe P e non si hanno infiniti processori o non si è fortunati. Per vedere quando P=NP, si guarda alla sottoclasse di NP dove ci sono i problemi NP-completi (aurdui). E' stato provato che o tutti i problemi NP-completi sono in P oppure non lo è nessuno. Questo è molto importante perchè molti problemi pratici sono stati classificati come NP-completi.

Fino a che P non è uguale a NP non ci possono essere algoritmi che risolvono tutti i problemi soddisfacibili in tempo polinomiale.