Clases de complexidá P y NP
From Wikipedia, the free encyclopedia
La rellación ente les clases de complexidá P y NP ye una entruga que la teoría de la complexidá computacional entá nun pudo responder. N'esencia, la entruga ¿ye P = NP ? significa: si ye posible "verificar" rápido soluciones positives a un problema del tipu SI/NON (onde "rápido" significa "en tiempu polinómico"), ¿ye qu'entós tamién se pueden "llograr" les respuestes rápido?
Esti artículu necesita wikificase. |
Los recursos comúnmente estudiaos en complexidá computacional son:
– El tiempu: por aciu un aproximamientu al númberu de pasos d'execución qu'un algoritmu emplega pa resolver un problema.
– El espaciu: por aciu un aproximamientu a la cantidá de memoria utilizada pa resolver el problema.
Los problemes clasificar en conxuntos o clases de complexidá (L, NL, P, PCompleto, NP, NP-Completu, NP Duru...). Esti artículu va centrar nes clases P y NP.
Considérase'l problema más importante nesti campu, el Clay Mathematics Institute ufiertó un premiu d'un millón de dólares d'Estaos Xuníos para quien desenvuelva la primer demostración correuta.