La clase de complejidad P es un subconjunto tanto de NP como de co-NP y se piensa que la inclusión es estricta en ambos casos. Se piensa también que NP y co-NP son diferentes. De ser cierto esto, ningún problema de NP-completo podría estar en co-NP y ningún problema de co-NP-completo podría estar en NP.
Esto se demuestra como sigue: Si hubiera un problema en NP-completo y en co-NP al mismo tiempo, todo problema de NP se reduciría en él, se deduce que para todo problema en NP se podría construir una máquina de Turing no determinista que decidiera el problema complementario en tiempo polinómico, es decir, NP sería un subconjunto de co-NP y, por tanto los complementos de NP serían subconjunto de los complementos de co-NP, es decir, co-NP sería un subconjunto de NP, Por tanto NP y co-NP serían el mismo conjunto. De forma simétrica se demuestra que ningún problema en co-NP-completo puede estar en NP.
Datos:Q955748
Mayo 26, 2022
teoría, complejidad, computacional, clase, complejidad, conjunto, problemas, decisión, complementarios, clase, problema, complementario, entiende, aquel, cuyas, respuestas, positiva, negativa, están, invertidas, clase, complejidad, subconjunto, tanto, como, pi. En teoria de la complejidad computacional la clase de complejidad co NP es el conjunto de los problemas de decision complementarios a los de la clase NP Por problema complementario se entiende aquel que cuyas respuestas positiva o negativa estan invertidas La clase de complejidad P es un subconjunto tanto de NP como de co NP y se piensa que la inclusion es estricta en ambos casos Se piensa tambien que NP y co NP son diferentes De ser cierto esto ningun problema de NP completo podria estar en co NP y ningun problema de co NP completo podria estar en NP Esto se demuestra como sigue Si hubiera un problema en NP completo y en co NP al mismo tiempo todo problema de NP se reduciria en el se deduce que para todo problema en NP se podria construir una maquina de Turing no determinista que decidiera el problema complementario en tiempo polinomico es decir NP seria un subconjunto de co NP y por tanto los complementos de NP serian subconjunto de los complementos de co NP es decir co NP seria un subconjunto de NP Por tanto NP y co NP serian el mismo conjunto De forma simetrica se demuestra que ningun problema en co NP completo puede estar en NP Datos Q955748 Obtenido de https es wikipedia org w index php title Co NP amp oldid 117254379, wikipedia, wiki, leyendo, leer, libro, biblioteca,
