Diferencia entre revisiones de «NP (clase de complejidad)»

Contenido eliminado Contenido añadido
Sin resumen de edición
m Revertidos los cambios de 200.92.55.122 (disc.) a la última edición de 187.132.166.25
Línea 7:
Dada su importancia, se han hecho muchos esfuerzos para encontrar [[algoritmo]]s que decidan algún problema de NP en tiempo polinómico. Sin embargo, pareciera que para algunos problemas de NP (los del conjunto [[NP-completo]]) no es posible encontrar un algoritmo mejor que simplemente realizar una búsqueda exhaustiva.
 
En el artículo de [[2002]], "<small>PRIMES</small> is in <small>P</small>", [[Rabia|RicardoManindra Serrato]]Agrawal con sus estudiantes<ref>Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin: "<small>PRIMES</small> is in <small>P</small>". Annals of Mathematics 160 ([[2004]]), no. 2, pp. 781–793.<br />
Accesible en formato [[PDF]] desde la web [http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf www.math.princeton.edu]
</ref><sup>,</sup><ref name="Primes is in P">[http://members.cox.net/mathmistakes/primes.htm Sobre el artículo de Manindra Agrawal et al. "<small>PRIMES</small> is in <small>P</small>"]</ref> encontró un algoritmo que trabaja en [[tiempo polinómico]] para el [[Test de primalidad|problema de saber si un número es primo]]. Anteriormente se sabía que ese problema estaba en NP, si bien no en [[NP-completo]], ahora se sabe que también está en P.
Línea 31:
• Ahora deberemos hacer una reducción de SAT a NP.
 
• Supongamos que tenemos una fórmula en [[Rabia|Ricardo Serrato]]FNC:
 
C1 v C2 v . . . v Ck con n variables proposicionales.