Wikipedia

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

Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Matdrodes (discusión · contribs.)
151 725 ediciones
Revertir a la revisión 17739378
Línea 13:
[[Imagen:P_NP_y_NP-completo.png|thumb|right|350px|Diagrama de clases de complejidad. Si '''P''' = '''NP''', '''P''' contendría las zonas '''NP''' y '''NP'''-completo.]]
 
En este problema la clase de los problemas [[NP-completo]]s que pueden ser descritos como los problemas en '''NP''' que tienen menos posibilidades de estar en '''P''' (Ver [[NP-completo]] para una definición precisa). Actualmente los investigadores piensan que las clases cumplen con el diagrama mostrado por lo que P y NP-completo tendrían intersección vacía.
 
La importancia de la pregunta '''P''' = '''NP''' radica en que de encontrarse un algoritmo en P para un problema NP-completo, todos los problemas NP-completos (y por ende, todos los problemas de NP) tendrían soluciones en tiempo polinómico.
Obtenido de «https://es.wikipedia.org/wiki/P_(clase_de_complejidad)»