computer science - big - Problemas de ejemplo no en P ni en NP-completo sino en NP
o n !) (4)
Me gustaría saber un ejemplo de un problema que no está en P, ni en NP-completo, sino en NP.
Yo también; Si encuentra uno, siga adelante y visite esta página web para reclamar su premio de $ 1M: http://www.claymath.org/millennium/P_vs_NP/
Tengo un curso llamado Análisis de algoritmos en la universidad, donde actualmente estamos estudiando las diferentes clases de complejidad: P, NP, NP-hard, etc.
Ya hemos discutido los problemas de NP-completa como la intersección entre NP y NP-hard, y los problemas de P, contenidos en NP. También hemos hablado de algunos ejemplos, principalmente de problemas de NP-completos (k-coloring, k-clique, SAT).
La mayoría de las veces, demostramos que un problema es NP-completo por:
a. Encontrar un algoritmo no determinista para resolverlo (que usa elección, éxito, falla);
segundo. Reduciendo un problema conocido de NP-completo.
El problema es que estos problemas, cuando se ejecutan en una máquina determinista (secuencialmente, en lugar de bifurcarse simultáneamente cuando se encuentran con una opción) tienen soluciones de tiempo exponencial.
Mi pregunta es la siguiente: nunca he encontrado problemas que no se resolvieran ni en tiempo polinomial ni en tiempo exponencial; Los problemas de tiempo polinómico están en P y los problemas de tiempo exponencial generalmente están en NP-completo.
Aquí hay un útil diagrama de Venn: http://en.wikipedia.org/wiki/Np_complete
Me gustaría saber un ejemplo de un problema que no está en P, ni en NP-completo, sino en NP .
Además, ¿hay problemas intrínsecamente exponenciales, como generar el conjunto de potencia de un conjunto NP-completo? ¿O ese nombre solo se aplica a los problemas para los cuales se usa un algoritmo de tiempo exponencial solo porque no hay otro método obvio para resolverlo?
Ok, entonces le di la respuesta a Rosh Oxymoron porque en realidad enumeró algunos ejemplos de problemas que se sospecha que están entre P y NPC. Gracias por su ayuda, y me di cuenta de que hice esta pregunta en el lugar equivocado. También hay: https://cstheory.stackexchange.com/
donde encontré las siguientes respuestas muy útiles a mi pregunta: https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc que trata específicamente sobre lo que pregunté, y: https://cstheory.stackexchange.com/questions/52/hierarchies-in-np-under-the-assumption-that-p-np que es generalmente interesante, si no está relacionado exactamente con la pregunta inicial.
Muchas gracias,
Dan
- Se cree que los problemas de BQP, como la factorización de enteros y el logaritmo discreto (craqueo de RSA y DSA) están fuera de P y también se sospecha que están en NP pero no en NP-completa. Se sabe que la factorización de enteros está en NP, y se supone que está fuera de P y NP-completa.
http://en.wikipedia.org/wiki/BQP
http://en.wikipedia.org/wiki/Integer_factorization
- NP es un subconjunto de EXPTIME, pero se espera que NP! = EXPTIME (es decir, los problemas completos de EXPTIME no están en NP). Al igual que con P = NP, esto aún no está probado (pero se sabe que P! = EXPTIME). Por ejemplo, verificar si un algoritmo sería la mitad después de k pasos es EXPTIME-complete. Encontrar el conjunto de potencia es demasiado (obviamente).
No hay ningún problema conocido en
NP / NPC.Un problema está en NP si y solo si una máquina de navegación no determinística puede resolverlo en tiempo polinomial (o, de manera equivalente, una máquina de turisticación determinista puede decidirlo en tiempo polinomial). Este no es el caso de tu ejemplo.
Además, debe señalarse que no sabemos si
P = NP, por lo que es perfectamente posible (si es altamente improbable) que todos los problemas enNPse puedan resolver en tiempo polinomial. Entonces, si sabemos que un problema no se puede resolver en tiempo polinomial, ese problema no está en NP o, si podemos demostrar que sí lo está en NP, simplemente mostramos queNP != P