No estoy seguro de que haya equipos que estén trabajando seriamente en resolver P vs NP. Al menos, no he conocido ni oído hablar de ninguno …
Creo que la razón de esto se explica mejor usando la psicología en lugar de las matemáticas. Veamos los dos logros matemáticos más impresionantes de la historia reciente:
- Andrew Wiles probando el último teorema de Fermat
- Grigori Perelman demostrando la conjetura de Poincare
En ambos casos, tiene un problema realmente muy difícil que fue resuelto por la intensa pasión de un individuo, no de un equipo. Y lo que quiero decir con eso es que tanto Wiles como Perelman estaban lo suficientemente obsesionados con el problema en el que estaban trabajando, que se convirtió en el propósito de toda su existencia.
- ¿Volver a la Universidad para estudiar Matemáticas me ayudará a comprender completamente la lógica del algoritmo de la IA y la Programación Funcional?
- ¿Cuáles son algunas historias menos conocidas sobre Alan Turing?
- ¿Por qué no funciona mi función de búsqueda binaria?
- Recientemente he entregado mis tableros (12) y quiero hacer una mecánica BTech. Espero 85% en tableros, pero estoy seguro de que no romperé el avance de IIT. ¿Qué debo hacer, dejar un año y tomar clases de IIT o elegir la universidad solo este año? ¿Es seguro dejar caer un año?
- ¿Qué hace 'return 0' en este código a continuación?
¿Podría un equipo haber producido los mismos resultados? En teoría sí, pero en la práctica no. Los equipos, como construcción social, difunden la responsabilidad individual. Pero para tener el tipo de pasión que tenían Wiles y Perelman, debes sentir que tienes tanto el problema, que seguirás trabajando en él incluso si el mundo entero te excluye del ostracismo. Básicamente, es un nivel de pasión tan obsesivo que raya en la locura.
Esto no quiere decir que Wiles o Perelman no se hayan beneficiado de las ideas de otros matemáticos: las matemáticas no ocurren en el vacío, y otros matemáticos sentaron las bases para los impresionantes logros de Wiles y Perelman. Sin embargo, al final del día, sabemos que ni el último teorema de Fermat ni la conjetura de Poincare se habrían resuelto sin individuos dispuestos a hacer un esfuerzo minucioso para encontrar conexiones que nadie más vio o no quiso buscar.
Y dado que la mayoría de los informáticos creen que el problema P vs NP es de una dificultad comparable al último teorema de Fermat y la conjetura de Poincare, creo que esperamos que se resuelva de la misma manera (si es que lo hace).
¡Básicamente, requerirá a alguien que quiera dedicar su vida al problema!
No he visto a muchas personas inscribirse en ese desafío, aunque es probable que haya algunos que lo estén pero que lo mantengan en secreto para evitar el ridículo.
Dicho esto, es muy posible que el problema P vs NP no sea tan difícil de resolver como el último teorema de Fermat o la conjetura de Poincare, pero puede ser que el problema P vs NP no haya atraído a la clase correcta de matemáticos para resolverlo. . Algo a considerar es que la informática teórica está bastante separada del resto de las matemáticas.
La mayoría de nosotros pasamos más tiempo hablando con otros informáticos que con otros matemáticos, incluso si nos consideramos más parientes con los matemáticos. Y la informática es una disciplina que se basa fundamentalmente en el “ahora” y la practicidad de obtener gratificación instantánea en la academia.
Tal mentalidad puede dificultar la capacidad de resolver problemas matemáticos realmente desafiantes. No diría que TCS está completamente influenciado por esta mentalidad, pero puede ser suficiente para evitar que realice sus tareas más importantes.
La mayoría de los investigadores de TCS que conozco preferirían trabajar en problemas seguros que cumplan con dos criterios:
- Existe una posibilidad razonable de que el investigador pueda resolver el problema.
- Resolver el problema traerá una cantidad decente de reconocimiento.
En términos de objetivos de investigación, abordar P vs NP ciertamente satisface (2) pero falla miserablemente en (1). Entonces, lo que veo que la mayoría de los investigadores de la teoría de la complejidad hacen es trabajar alrededor de P vs NP, abordando problemas que algún día pueden ayudar con P vs NP pero que todavía se consideran manejables. No creo que nadie en el campo piense que tienen una seria posibilidad de tropezar con la solución de P vs NP de esta manera, pero esperan que lo que estén haciendo sentará las bases para que alguien más lo resuelva. Desafortunadamente, este enfoque conservador incremental para la investigación puede no ser lo que realmente se necesita para resolver P vs NP.
El esfuerzo más ambicioso que he visto hasta la fecha específicamente para abordar P vs NP es lo que hizo Ketan Mulmuley al establecer el programa de Teoría de Complejidad Geométrica. Este esfuerzo fue ciertamente muy ambicioso, ya que no es obvio que GCT sirve para cualquier propósito de la informática además de tratar de resolver P vs NP, y el propio Mulmuley no tiene esperanzas de que incluso con GCT, P vs NP se resuelva en menos de 100 años. .
Este puede o no ser el enfoque correcto, pero hasta la fecha ha recibido la mayor atención, porque nadie más en la comunidad de TCS ha dicho que se están centrando en un esfuerzo legítimo para resolver P vs NP. De hecho, ha habido más esfuerzos en TCS para mostrar que la mayoría de los esfuerzos para resolver P vs NP serán inútiles.
Me parece que TCS es, en general, un lote bastante pesimista. Tal vez, es por eso que la mayoría se ha quedado con la suposición negativa de P no igual a NP, a pesar de muchos ejemplos en matemáticas no constructivas de cosas que son verdaderas pero contra-intuitivas. Me imagino que la mayoría de las personas en TCS, moralmente, no apreciaría realmente una prueba no constructiva de que P = NP porque desde un sentido práctico es casi tan malo como no saber la respuesta.
Además, en términos prácticos, si P = NP pero el único algoritmo que podemos encontrar para resolver problemas NP-Completos es O (n ^ M) donde M es una constante mayor que el número de átomos en el universo, entonces la mayoría de las personas con TCS saben sus colegas que trabajan en áreas prácticas de la informática pondrán los ojos en blanco ante esa respuesta. Ni siquiera estoy seguro de si tal resultado obtendría un Premio Turing, porque no ofrece nada ni remotamente útil para la informática, excepto para decir que el problema P vs NP probablemente se formuló incorrectamente para empezar. A los filósofos, matemáticos e incluso físicos, les importará, pero no a los informáticos.
Nunca conocí a Mulmuley, así que no puedo saber cuánto interés personal tiene en resolver P vs NP. Por lo que escuché, tengo la impresión de que él es algo serio sobre resolver P vs NP, pero probablemente no en la misma medida en que Wiles y Perelman se referían a sus problemas. No creo que esté interesado en resolver el problema él mismo, sino en atraer a otros investigadores para que lo analicen.
Dado que GCT vincula la teoría de la complejidad con la geometría algebraica, asumiría que una de sus esperanzas es atraer a matemáticos brillantes fuera de TCS para tratar de resolver el problema P vs NP. El último teorema de Fermat se resolvió utilizando geometría algebraica, y la mayoría de los intentos de hipótesis de Riemann y otros problemas de teoría de números difíciles utilizan geometría algebraica.
No estoy seguro de si esto indica que la geometría algebraica es más útil que otras áreas de las matemáticas para resolver problemas difíciles, pero creo que puede indicar que los matemáticos brillantes que tienden a resolver problemas imposibles pasarán mucho tiempo familiarizándose con ellos. geometría algebraica, solo porque hay un precedente de geometría algebraica utilizada para resolver problemas casi imposibles.
De todos modos, no sé si el programa GCT de Mulmuley ha tenido éxito al atraer a matemáticos que no son TCS al problema P vs NP. Si hay algunos que están gastando un gran esfuerzo en resolver P vs NP en este momento, lo más probable es que lo mantengan en secreto.
El único matemático famoso criado fuera de TCS que conozco, que ha mostrado mucho interés en P vs NP, es Terence Tao. Pero aunque Tao podría ser lo suficientemente inteligente como para resolver P vs NP, dudo que sea él quien realmente lo haga. Parece demasiado cuerdo para tirar el resto de su carrera matemática, y todo el prestigio que conlleva, y dedicar el resto de sus primeros años matemáticos a resolver P vs NP. Por supuesto, supongo que el hecho de que Tao haya analizado el problema y no lo haya resuelto es evidencia de que puede ser al menos tan difícil como el último teorema de Fermat y la conjetura de Poincare.
Por lo tanto, P vs NP probablemente será resuelto por alguien que sea brillante pero aún no famoso, que tenga poco que perder si fracasan y que realmente no le importe la fama, que sea extranjero para la comunidad de TCS y que se ajuste principalmente a Descripción matemática solitaria estereotipada.
Para aumentar las posibilidades de que esto suceda, TCS debe ser menos aislacionista.
TLDR: Creo que las barreras psicológicas y sociológicas son la razón principal por la que P vs NP sigue sin resolverse.
