Home

NPcompleto

NP-completo, o problemas NP-completos, es una clase de problemas de decisión en la teoría de la complejidad computacional. Un problema es NP-completo si pertenece a NP, es decir, si una solución dada puede verificarse en tiempo polinomial, y además es NP-hard, lo que significa que cualquier problema en NP puede reducirse en tiempo polinomial a él. En otras palabras, es tan difícil como los problemas más difíciles en NP.

Las reducciones polinómicas permiten transferir la dificultad: si A se reduce a B en tiempo polinomial y

La existencia de problemas NP-completos implica que, en la práctica, no se espera encontrar algoritmos de tiempo

Históricamente, NP-completo fue introducido de forma independiente por Stephen Cook y Leonid Levin a principios de

B
es
NP-completo,
entonces
A
es
NP-completo.
Cook
y
Levin
demostraron
que
el
problema
SAT
es
NP-completo;
desde
entonces
se
han
mostrado
muchos
otros
problemas
NP-completos,
como
3-SAT,
Vertex
Cover,
Hamiltonian
Cycle,
CLIQUE
y
Subconjuntos
de
suma
(Subset
Sum)
en
su
versión
de
decisión,
entre
otros.
También
existen
variaciones
como
el
problema
del
viajante
de
comercio
en
su
versión
de
decisión.
polinomial
para
resolver
todos
los
casos
de
estos
problemas,
a
menos
que
P
sea
igual
a
NP.
Por
ello,
la
investigación
se
centra
en
algoritmos
heurísticos,
métodos
de
aproximación,
soluciones
exactas
para
instancias
pequeñas
y
enfoques
de
complejidad
paramétrica.
la
década
de
1970.
Desde
entonces,
la
noción
se
ha
convertido
en
un
pilar
para
entender
los
límites
de
la
computación
eficiente.