Clases de complejidad P y NP

La relación entre las clases de complejidad NP y P es una pregunta por primera vez formulada por el científico computacional Stephen Cook que la teoría de la complejidad computacional aún no ha podido responder.En esencia, la pregunta <<¿es P = NP completo?>> significa: <– El espacio: mediante una aproximación a la cantidad de memoria utilizada para resolver el problema.por ejemplo, ¿Existe un subconjunto del conjunto {−2, −3, 15, 14, 7, −10} tal que la suma de sus elementos sea 0?Una respuesta a la pregunta P = NP sería determinar si en problemas del tipo SUMA-SUBCONJUNTO es tan fácil hallar la solución como verificarla.La restricción a problemas de tipo SÍ/NO realmente no es importante; aún si se permiten respuestas más complicadas, el problema resultante resulta equivalente (o sea si FNP = FP).Por lo tanto, la principal pregunta aún sin respuesta en la teoría de la computación está referida a la relación entre estas dos clases: En una encuesta realizada en el 2002 entre 100 investigadores, 61 creían que la respuesta era NO, 9 creían que la respuesta era SI, 22 no estaban seguros, y 8 creían que la pregunta podía ser independiente de los axiomas actualmente aceptados, y por lo tanto imposible de demostrar por el SI o por el NO.pasos, donde k y c son constantes independientes del conjunto de datos, entonces se dice que el problema puede ser resuelto en tiempo polinómico y lo clasificamos como perteneciente a la clase P. En forma intuitiva, consideramos que los problemas contenidos en P son aquellos que pueden ser resueltos en forma razonablemente rápida.P suele ser la clase de problemas computacionales que son “eficientemente resolubles” o “tratables”, aunque haya clases potencialmente más grandes que también se consideran tratables, como RP Y BPP.Aunque también existen problemas en P que no son tratables en términos prácticos; por ejemplo, unos requieren al menosEn forma intuitiva, se puede pensar que NP es un problema de decisión que es difícil de resolver si no se posee ningún otro dato o información adicional.Sin embargo, si se recibe la información adicional llamada un certificado, entonces el problema puede ser resuelto fácilmente.Por ejemplo, si se nos da el número 323 y se nos pregunta si 323 es un número factorizable, sin darnos ningún dato o información adicional, deberíamos hacer la raíz cuadrada de 323 (+/-17.9722) redondear al entero menor en valor absoluto (17) e intentar dividir desde 17 a 2.Sin embargo, si se nos da el número 17, podemos dividir 323 por 17 y rápidamente verificar que 323 es factorizable.El proceso de división para verificar que 323 es factorizable es en esencia una máquina Turing y en este caso es denominado el verificador para 323.Formalmente, se define NP como un conjunto de lenguajes que satisfacen ciertas condiciones., se satisfacen las siguientes condiciones: Entonces, la máquina de Turing que decideAunque no está demostrado, la mayor parte de los expertos creen que esto es un subconjunto estricto.De todas las clases mostradas arriba, sólo se conocen dos contenciones estrictas:Si esta contiene a P, la jerarquía polinomial se colapsa con el segundo nivel.Por otra parte, esta también contiene algunos algoritmos poco prácticos, incluyendo algunos problemas no decidibles.Propiedades Los algoritmos de tiempo polinómico son cerrados respecto a la composición.La clase NP está compuesta por los problemas que tienen un certificado sucinto (también llamado testigo polinómico) para todas las instancias cuya respuesta es un SÍ.La única forma de que tengan un tiempo polinomial es realizando una etapa aleatoria, incluyendo el azar de alguna manera para elegir una posible solución, y entonces en etapas posteriores comprueba si esa solución es correcta.En otras palabras, dada una solución para una cierta instancia, es posible comprobar que es válida en TIME (n^k).La co-P está compuesta por los problemas que tienen un contraejemplo sucinto para todas las instancias cuya respuesta es NO.Basándonos solo en esta idea, no es obvio que exista un problema NP-completo.Sin embargo, después se demostró que el problema era NP-completo, la prueba por reducción, proporcionó una manera más simple de demostrar que muchos otros problemas están en esta clase.Se han publicado muchos artículos intentando resolver el problema P vs NP.