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
[Modifega | modifica 'l sorgent]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
[Modifega | modifica 'l sorgent]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
[Modifega | modifica 'l sorgent]- P (class de complessità)
- NP (class de complessità)
- Co-NP
- Macchina del Turing minga deterministica
- Problema de la fermada