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>",
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
C1 v C2 v . . . v Ck con n variables proposicionales.
|