Primero, permítanme ofrecerles la advertencia de que es poco probable que exista una solución práctica que funcione de manera consistente en un período de tiempo razonable. Un uso más práctico del tiempo sería buscar una prueba de P! = NP en lugar de buscar soluciones prácticas que funcionen para todos los conjuntos de problemas. Tenga en cuenta que, en la práctica, la heurística funcionará muy bien en muchos problemas P vs. NP en una amplia variedad de casos, pero existe un enfoque de confrontación que alguien podría usar para construir siempre contraejemplos a menos que NP = coNP (esto es un problema relacionado conjetura, y la mayoría de los teóricos suponen NP! = coNP).
Suponiendo que, por alguna casualidad sorprendente, descubra que su algoritmo es capaz de resolver problemas de NP-Complete de manera consistente en una cantidad de tiempo razonable (es decir, polinomio razonablemente pequeño). En aras de la especificidad, suponga que puede resolver el problema 3SAT en una cantidad de tiempo proporcional a n ^ p para un pequeño valor de p, y donde n es el número de cláusulas en 3SAT. Entonces aquí están algunas de las aplicaciones:
- Dado un predicado P tal que existe una prueba de P en la teoría de conjuntos estándar, y la prueba más corta requiere M bits de espacio para derivar, en realidad puede encontrar la prueba en una cantidad de tiempo como M ^ (p + epsilon) donde epsilon es una constante pequeña (entera). En resumen: puede probar casi todos los demás problemas abiertos en matemáticas, incluidos (probablemente) los problemas restantes del Milenio.
- Puede romper las técnicas criptográficas modernas que no dependen de la computación cuántica. En efecto, puede destruir BitCoin, y puede destruir la comunicación segura a través de la web, y puede destruir las técnicas actuales para enviar dinero de manera segura utilizando firmas digitales.
- Puede mejorar radicalmente los diseños de placas de circuito y VLSI, ofreciendo de manera efectiva otro aumento en la computabilidad total.
- Puede resolver problemas de plegamiento de proteínas para diseñar nuevos medicamentos y tomar minutos u horas en lugar de años.
Esto es realmente solo una pequeña muestra. En resumen, cambiaría radicalmente el mundo.
- Soy un estudiante de primer año de CS, no puedo resolver programas simples, ¿cómo puedo realmente mejorar mis habilidades algorítmicas de resolución de problemas?
- ¿Cómo se puede resolver la enfermedad de la realidad virtual?
- Si pudiera obtener 8 bits (1 byte) de información de un oráculo que conoce el futuro dentro de 50 años, ¿qué pregunta o preguntas haría?
- ¿Es posible desarrollar aplicaciones a tiempo completo sin un título?
- Para aplicaciones web grandes, ¿dónde se almacenan los datos de aprendizaje automático?
Además, desafiaría una cierta intuición que encontramos en la vida cotidiana: a menudo es más fácil reconocer y comprender una solución a un problema que encontrar una solución desde cero. Si P = NP, o si el problema es de alguna manera práctico, hay muy poca diferencia entre aprender una solución y encontrarla por su cuenta.
