P vs NP

El problema de P vs NP a l'è vun di problema vert pussee important de l'informatega, e l'è anca vun di problema del millenni, l'unich a tema informategh. In pratica, se l'è ver, el dis che ogni problema che i sò soluzion pòden vess verificaa velocement de 'n computer pòden vess anca calcolaa velocement.

 Spiegazion 
I problema de tipo NP a hinn quij problema che i sò soluzion pòden vess calcolaa de ona macchina del Turing minga deterministica in d'on temp polinomial. On esempi a l'è el problema de la fattorizzazion, che incoeu l'è resolvibil polinomialment domà cont on computer quantich e l'algoritm de fattorizzazion de  Shor.

Inveci i problema de tipo P a hinn ona sottaclass de quej NP e hinn tucc quej problema che i sò soluzion pòden vess calcolaa de ona macchina del Turing normal in d'on temp polinomial. Di esempi a hinn el calcolà del massim comun divisor o, comé dimostraa in del 2002, savè se on numer a l'è primm.

 Possibil influenz 
Se 'l fuss verificaa che P = NP a ghe sarien di important cambiament in l'informatega.

Per esempi incoeu la pupart di problema de crittografia se fonden in su la possibilità de fà a la svelta di operazion 'me la moltiplicazion ma de vègh besogn de provà tucc i combinazion per rivà a fà la fattorizzazion o el logaritm discrett.

Se donca el fuss provaa che anca 'sti problema chi a hinn resolvibil in P a ghe saria de rielaborà la pupart de la crittografia, anca se gh'è la possibilità che 'l fuss in problema NP hard, e donca gramm de resoeulv istess.

 Vos correlaa 
P (class de complessità)
NP (class de complessità)
Co-NP
Macchina del Turing minga deterministica
Problema de la fermada

 Riferiment 
Clay- P vs NP problem 
P vs NP explained 
Explained: P vs. NP
What Does 'P vs. NP' Mean for the Rest of Us?
Categoria:Teoria de la calcolabilità