P versus NP: diferència entre les revisions

En essència, la qüestió '''P''' = '''NP''' pregunta: si una solució positiva per un problema de SI/NO pot ser verificada ràpidament, poden calcular-se igual de ràpidament les respostes? Es presenta a continuació un exemple: Donat un conjunt d'[[Nombres_enters|enters]], existeix algun subconjunt que sumi 0? Per exemple, donat el conjunt {-2, 3, 8, 15, -10} existeix algun subconjunt que doni 0? La resposta es SI, tot i que pot costar un cert temps per trobar un subconjunt que ho faci - i si el el conjunt és gran, es pot tardar molt de temps a trobar-lo. Per altre banda, si algú afirma que la resposta es "SI, perquà {-2, -3, -10, 15} sumen zero", llavors podem comprovar-ho amb molt poques operacions simples. Verificar que un conjunt suma zero es molt més ràpid que trobar el subconjunt de la primera solució. La informació necessària per verificar una solució positiva s'anomena certificat. Podem concloure que donat el certificat adient, respostes positives al nostre problema es poden verificar ràpidament (en temps polinomial) i és per això que aquest problema pertany a la classe '''NP'''.