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.

Quest articol chì l'è scrivuu in lombard, grafia milanesa.

Diagramma cont P ≠ NP

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 Arqiviad qé:
• P vs NP explained
• Explained: P vs. NP
• What Does 'P vs. NP' Mean for the Rest of Us?