Creo que estás confundiendo los conceptos. Los problemas sobre los cuales uno puede preguntarse “qué tan eficientemente una computadora puede resolverlos” son los problemas en los que la computadora debe tomar una entrada y devolver el resultado del cálculo para esa entrada. Por ejemplo, el problema “Es un número primo”, el problema es crear un algoritmo que tome el número 5 y diga “SÍ”, tome el número “20” y diga “NO” – “resolver un problema” significa crear un algoritmo que siempre devuelve la respuesta correcta. Este es también el tipo de problemas que se pueden colocar en las clases P y NP.
El problema “P vs NP” es completamente independiente de esa noción de “problema algorítmico”. Esta es solo una declaración que puede ser verdadera o falsa (o independiente de los axiomas), pero si alguien alguna vez demuestra que es verdadera o falsa, está hecha, conocemos la respuesta y no intentaremos resolverla nunca más. No tiene sentido crear algoritmos o preguntar qué tan eficientemente puede resolverlo (por supuesto, si queremos resolverlo por computadora, entonces es razonable preguntar qué tan rápido se puede hacer, pero la noción de eficiencia del algoritmo no puede se aplicará si solo tenemos una entrada que nos interesa, entonces es solo el momento de la computación), es más como si usted preguntara qué tan eficientemente una computadora puede verificar si 25 es primo. Bueno, al instante, porque sabemos que 25 no es primo, por lo que podemos devolver la respuesta no en O (1). Ahora, si creamos un algoritmo que verifica si el número es primo, también podemos aplicarlo al caso específico 25. De manera similar, para el caso específico “es P vs NP verdadero”, la solución genérica habría sido, por ejemplo, la solución a un problema “crea un algoritmo que pueda probar o refutar un teorema matemático”. Por supuesto, no significa que debamos idear un algoritmo de este tipo para probar P vs NP, pero esa es la diferencia crucial entre el problema algorítmico y el problema de resolver un caso específico, por ejemplo, un teorema matemático.
Sin embargo, puede haber varias preguntas que hacer en lugar de la del tema:
- ¿Cómo se descubre la estructura en patrones bidimensionales?
- Cómo representar más de la cantidad predeterminada de dígitos en números como (1/7) en Python
- ¿Cuáles son los problemas finales más interesantes del cálculo?
- ¿Qué debo saber sobre las matemáticas combinadas con el desarrollo web (programación)?
- ¿Alguien ha explorado el uso de autómatas celulares 2D en una superficie esférica sintonizada para proyectar un universo 3D dentro que simule la gravedad?
1. ¿Es posible que Quantum Computer resuelva el problema P vs NP?
Esperar que tengamos una IA mucho más poderosa que cualquier otra que tengamos hoy, considerando que ese es el problema que los mejores investigadores humanos pasaron años intentando sin resultado. Por supuesto, la computadora cuántica puede ayudar a mejorar las IA, pero ciertamente no me parece que pueda ser ese factor importante en comparación con el resto del trabajo que se debe hacer en el campo de la IA.
2. ¿Es posible que un ser humano resuelva el problema P vs NP creando un algoritmo cuántico polinómico para un problema NP completo?
No. Las clases P y NP no se definen como “lo que nuestra mejor computadora existente en el mundo puede resolver en tiempo polinómico”, sino en modelos específicos bien definidos, por lo que la invención de la computadora cuántica es completamente irrelevante para el problema P vs NP, que es inherentemente vinculado con los modelos asociados con nuestra noción de cálculo no cuántica “estándar”. La computación cuántica tiene sus propias clases BQP y QMA (aunque BQP se parece más a BPP en modelos estándar que a P. Pero de todos modos no sabemos la respuesta a BPP vs NP) y es un problema equivalente BQP vs QMA.
3. ¿Es posible que un humano presente un algoritmo cuántico polinómico para un problema NP-completo, sin cambiar nada en el estado del problema P vs NP, pero resolviendo lo que en la práctica es el conocimiento más importante sobre los problemas NP para ¿Es decir, si somos capaces de resolver problemas de NP en tiempo polinómico?
Si, posiblemente. Hasta ahora no conocemos la relación entre NP y BQP, por lo que, en particular, no podemos excluir la posibilidad de que todos los problemas de NP puedan resolverse en tiempo polinómico con probabilidad de error limitada en una computadora cuántica (BQP). Por lo que deduzco, se cree firmemente que no es cierto al igual que P = NP no es cierto, pero no lo sabemos. Por lo tanto, alguien puede probar algún día que es posible o no posible resolver polinomialmente problemas NP completos en una computadora cuántica. Sin embargo, vale la pena enfatizar que lograrlo no está asociado con la creación de una computadora cuántica, ese es solo el teorema que podemos probar sobre la computación cuántica, independientemente de que la computadora cuántica existente ya esté construida o no.
“¿Hay algún artículo académico en línea que relacione estas cosas?”. Mi conocimiento de ese tema es tristemente muy informal y no puedo decirle cosas mucho más profundas, pero creo que comenzar a buscar en Google los temas sobre las clases que mencioné (“BQP vs NP “, podría ser también” BQP vs QMA “, aunque probablemente sea menos) sería el punto de partida correcto en la búsqueda de artículos y desde allí probablemente pueda encontrar otros mencionados en publicaciones de blog sobre el tema, etc. interesado en pasar más tiempo.
