^^P vs NP

P

the problems that can be solved by a reasonable amount of time
es: multiplication, sorting (es: alphabetizing a list of names)

NP

the problems where, if you're given a correct solution you can at least check it in a reasonable amount of time

P vs NP

is P=NP ?
fun fact: proving this is an NP problem

NP-complete problems

tutti gli NP si possono riportare ad esso in polynomial time

P vs NP and the Computational Complexity Zoo

negli scacchi, anche se ci fosse detto la mossa migliore da fare, il verificarlo sarebbe praticamente impossibile a causa dell'enorme numero di mosse necessarie per verificarlo.

In un triangolo rettangolo

il quadrato sul lato sotteso all'angolo retto

e' uguale alla somma dei quadrati sui lati contenenti l'angolo retto.