P vs NP

De Wikipedia
Jump to navigation Jump to search
Lumbard ucidental Quest articol chì l'è scrivuu in lombard, grafia milanesa.
Diagramma cont P ≠ 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[Mudifega | mudìfica 'l sorgènt]

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[Mudifega | mudìfica 'l sorgènt]

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[Mudifega | mudìfica 'l sorgènt]

Riferiment[Mudifega | mudìfica 'l sorgènt]