He leído que para resolver la ecuación de Pell ni sabe que es en $P$ ni sabe que ser $NP$-completa. ¿Qué otros ejemplos naturales e importantes de este tipo de problemas?
Respuestas
¿Demasiados anuncios?
Ellos son llamados NP-intermedio problemas (bajo la suposición de $P\neq NP$, de lo contrario, la definición no tiene sentido).
Por ahora, algunos naturales/problemas del mundo real son sospechosos de estar en esta clase, sin embargo, nadie ha sido capaz de demostrar que, ya que sería una prueba de $P\neq NP$.
- Gráfico problema de isomorfismo, es decir, para determinar si dos grafos son isomorfos.
- Entero de la factorización y el problema de la computación del logaritmo discreto
se encuentran entre los más conocidos.
sliders_alpha
Puntos
168
Algún problema en la clase BQP como facturización del número entero se sospecha que fuera P, y no se conoce la relación entre BQP y NP.
De Wikipedia, la presunta relación de BQP a otros espacios del problema:
Arctictern
Puntos
85
Me gusta el PPAD ("Polinomio de Paridad de Argumentos en los gráficos") la complejidad de la clase, porque la clase de PPAD-completar los problemas incluye cosas como la búsqueda de los equilibrios de Nash y Brouwer fixpoints, así como su combinatoria análogos como Sperner' lexema. He aquí una cita de Wikipedia para poner las cosas en contexto:
PPAD es una clase de problemas que se cree que será duro, pero la obtención de PPAD-integridad es una débil evidencia de la dificultad que la de la obtención de NP-completitud. No obstante, puede darse el caso de que PPAD es la misma clase P, y todavía tiene que P≠NP, aunque parece poco probable.
La misma pregunta se ha hecho antes en TCS, y las respuestas no son superiores a cualquier cosa que yo podría venir para arriba con. Sin embargo, no pude resistir la tentación de añadir la referencia a la PPAD como una respuesta.
