^^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.