No puedo responder la pregunta sobre el realismo de una película que no he visto, pero es suficiente decir que las consecuencias de una prueba de P = NP, particularmente con una solución alrededor de O (n ^ 5) (suponiendo constantes razonables) Ser un resultado drástico.
Si tuviera una solución “real”, ¿podría estar en peligro? Potencialmente. Menos probable del gobierno de los Estados Unidos que de entidades extranjeras.
Para verificar su respuesta, y sí, realmente debería tratar de convencerse de que tiene una buena respuesta, use el resultado para resolver un problema que pueda factorizar números compuestos por dos números primos, cada uno con aproximadamente 1000 dígitos. Si tiene una solución para P = NP, debería poder hacer este ejercicio.
- ¿Cómo va a explicar la paravirtualización a un laico?
- ¿Cuál es el método de fuerza bruta?
- ¿Cuáles son las limitaciones / reglas de lo que el aprendizaje automático no puede hacer?
- ¿Qué tan importante es el conocimiento de las bases de datos en Machine Learning?
- ¿Cuál es la diferencia entre IoT y la informática ubicua?
Además, permítanme agregar que tengo una manera de construir directamente un contraejemplo para su solución, y mi contraejemplo será válido suponiendo NP! = Co-NP, y una suposición de dureza “razonable”. Tenga en cuenta que no he demostrado que mi mecanismo de contraejemplo sea correcto, pero considero que es una conjetura muy fuerte que es correcto. (El siguiente es un trabajo no publicado, a menos que cuente un blog interno que escribí mientras trabajaba para Google. No ha sido revisado por pares y puede tener fallas).
En aras de la especificidad, supondré que el problema NP-hard particular que ha resuelto es 3SAT. Si ha resuelto un problema diferente (no 3SAT), aún debería ser capaz de encontrar un medio para resolver 3SAT en tiempo polinómico ya que 3SAT es NP-completo.
Como tiene una solución para 3SAT, puede construir una máquina de Turing para representar su solución. Supongamos que una representación de cadena estándar de su máquina Turing tiene una longitud de N. Exigamos además que cuando su máquina Turing afirme que hay una asignación satisfactoria para una instancia del problema 3SAT, realmente escriba la asignación satisfactoria. Nuevamente, suponiendo que P = NP, esto es fácilmente posible. (Inicialmente, su solución podría decidir “satisfactoria o no”, pero luego puede usar esto marcando “¿sigue siendo satisfactoria cuando fuerzo esta variable booleana a VERDADERO? Si es así, continúe, de lo contrario, configure la variable falsa y continúe La siguiente variable).
Reclamación: Existe una instancia de problema de contraejemplo S de manera que S es una instancia de problema 3SAT válida y donde se cumple una de las siguientes condiciones:
- S no es satisfactoria, pero su máquina genera una asignación satisfactoria incorrecta.
- S es satisfactoria, pero su máquina no encuentra la tarea satisfactoria.
La afirmación adicional es que la longitud de S (el contraejemplo) es poli (N + 2) * (N + 2), donde el polinomio poli es su polinomio seleccionado durante el tiempo que su solución requiere (es decir, para su case, poly sería O (n ^ 5), por lo que el tamaño del contraejemplo sería O (n ^ 6)). (Por cierto, la elección de poli (N + 2) * (N + 2) es un poco pesimista. El ejemplo contrario podría encontrarse en O (N) con un conjunto razonable de constantes. Sin embargo, mi “conjetura” de poli (N + 2) * (N + 2) es una apuesta bastante segura, así que empiezo con eso).
Curiosamente, encontrar un contraejemplo dada esta configuración es un problema dentro de NP. Dado que el lenguaje de “contraejemplos” es un lenguaje en NP: el lenguaje toma como entrada una máquina de Turing, y el certificado de verificación es la cadena de contraejemplo S. Dado que el lenguaje de contraejemplo está en NP, para cada instancia del problema, en particular la instancia para su máquina Turing, hay una instancia correspondiente del problema 3SAT que será satisfactoria exactamente cuando haya un contraejemplo para su máquina.
Si realmente tiene una solución que demuestre P = NP, debe poder mostrar cómo la construcción de la instancia del problema que acabo de exponer no genera un contraejemplo para su idioma. Cuando se le da el problema en sí, debería encontrar que la instancia del problema no es satisfactoria.
