Wikipedia

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

Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Xqbot (discusión · contribs.)
Bots
532 776 ediciones
m robot Añadido: bg:NP-сложност; cambios triviales
Bilbo-b (discusión · contribs.)
110 ediciones
Mejora de estilo (El principio del artículo parecía extraido textualmente de un libro de texto)
Línea 1:
En [[complejidad computacional|teoría de la complejidad computacional]], '''NP''' es el acrónimo en [[idioma inglés|inglés]] de ''Polinómico no determinista'' (''Non-Deterministic Polynomial-time''). Es el conjunto de problemas que pueden ser resueltos en [[tiempo polinómico]] por una [[máquina de Turing]] no determinista.▼
Los recursos comúnmente estudiados en complejidad computacional son:
 
– El '''tiempo''': mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema.
 
– El '''espacio''': mediante una aproximación a la cantidad de memoria utilizada para resolver el problema.
 
En el análisis computacional, se requiere un modelo de la computadora para la que desea estudiar el requerimiento en términos de tiempo. Normalmente, dichos modelos suponen que la computadora es determinista (dado el estado actual de la computadora y las variables de entrada, existe una única acción posible que la computadora puede tomar) y ''secuencial'' (realiza las acciones una después de la otra). Estas suposiciones son adecuadas para representar el comportamiento de todas las computadoras existentes, aún incluye a las máquinas con [[programación paralela|computación en paralelo]].
 
Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P, P-Completo,NP, NP-Completo, [[NP-hard|NP Duro]]...).Nosotros nos vamos a centrar en la clase NP.
 
== La clase NP ==
 
▲En [[complejidad computacional|teoría de la complejidad computacional]], '''NP''' es el acrónimo en [[idioma inglés|inglés]] de ''Polinómico no determinista'' (''Non-Deterministic Polynomial-time''). Es el conjunto de problemas que pueden ser resueltos en [[tiempo polinómico]] por una [[máquina de Turing]] no determinista.
 
La importancia de esta clase de problemas de decisión es que contiene muchos problemas de búsqueda y de optimización para los que se desea saber si existe una cierta solución o si existe una mejor solución que las conocidas. En esta clase están el [[problema del viajante]] (también llamado ''"problema del agente de ventas"'' o ''"problema del agente viajero"'') donde se quiere saber si existe una ruta óptima que pasa por todos los [[nodo]]s en un cierto [[teoría de los grafos|grafo]] y el [[problema de satisfacibilidad booleana]] en donde se desea saber si una cierta fórmula de lógica proposicional puede ser cierta para algún conjunto de valores booleanos para las variables.
Obtenido de «https://es.wikipedia.org/wiki/NP_(clase_de_complejidad)»