¿Deberían los expertos en TCS cobrar dinero por leer pruebas de que P! = NP?

Es bien sabido que hay toneladas de aficionados, incluido yo mismo, que están interesados ​​en el problema P vs. NP. También hay muchos aficionados, incluido yo mismo, que han intentado resolver el problema.

Un problema que creo que sufre la comunidad TCS es una relación relativamente alta de interés-aficionado-experto; Esto lleva a que los expertos se vean inundados con pruebas de que P! = NP, y he leído que están frustrados y abrumados, de manera bastante comprensible, por esta situación. Oded Goldreich ha escrito sobre este tema e indicó su propia negativa a verificar las pruebas.

Al mismo tiempo, hablando desde el punto de vista de un aficionado, puedo afirmar que hay pocas cosas más frustrantes para los entusiastas de TCS de nivel no experto de cualquier nivel que generar una prueba que parece correcta, pero que carece de ambas la capacidad de encontrar el error en la prueba usted mismo y la capacidad de hablar con cualquier persona que pueda detectar errores en su prueba. Recientemente, RJ Lipton escribió sobre el problema de los aficionados que intentan ser tomados en serio.

Tengo una propuesta para resolver este problema, y ​​mi pregunta es si otros lo consideran razonable o no, o si hay problemas con él.

Creo que los expertos deberían cobrar una suma de dinero considerable pero razonable (por ejemplo, 200 - 300 USD) a cambio de aceptar leer las pruebas en detalle y encontrar errores específicos en ellas. Esto lograría tres cosas:

1. Los aficionados tendrían una forma clara de evaluar y tomar en serio sus pruebas.
2. Los expertos serían compensados ​​por su tiempo y energía gastados.
3. Se impondría un costo significativamente alto al comprobar que la cantidad de pruebas que presentan los aficionados se reduciría drásticamente.

Nuevamente, mi pregunta es si esta es o no una propuesta razonable. Obviamente, no tengo la capacidad de hacer que los expertos adopten lo que sugiero; Sin embargo, espero que los expertos lean lo que he escrito y decidan que es razonable.

Déjame responder a tu sugerencia con una contra sugerencia: ¿por qué no intentas establecer un negocio, actuando como intermediario entre aficionados y expertos? Los aficionados pagan para que se evalúen sus pruebas. Usted encuentra un experto y le paga al experto para que evalúe la prueba, tomando una parte del dinero para su papel de intermediario. Intentar administrar un negocio de este tipo es la forma más confiable de averiguar si su idea es factible.

Tengo algo de "experiencia en el mundo real" en esta industria naciente (y no, no estoy hablando de mi oferta de $ 200,000 a Deolalikar :-))

En enero, un desarrollador de software me envió un correo electrónico diciendo que tenía un intento de prueba de P ≠ NP, y que aunque estaba casi seguro de que había un error, no pudo encontrarlo. Me preguntó si conocía a algún estudiante de posgrado que estuviera dispuesto a encontrarle el error a cambio de unos cientos de dólares.

Para darle un poco de contexto: obtengo una prueba de P ≠ NP o P = NP en mi bandeja de entrada aproximadamente una vez al mes. Muchos de estos correos electrónicos van a una larga lista de teóricos de la complejidad (Cook, Karp, Fortnow, Sipser ...); a menudo incluyen reflexiones religiosas o metafísicas, así como pistas oscuras sobre conspiraciones académicas. (En un caso, hubo amenazas de muerte gráficas contra mí, lo que me llevó a contactar a la policía). Prácticamente ninguno de ellos reconoce ninguna posibilidad de que la prueba pueda estar equivocada o que el autor haya entendido mal la pregunta. Y cuando, en la escuela de posgrado, traté de mantener correspondencia con los autores, descubrí que todos ellos creían fervientemente en la máxima de Churchill "nunca, nunca, nunca, nunca te rindas".

¡Entonces la solicitud del desarrollador de software realmente me impresionó! Esta fue la primera vez que vi una prueba P ≠ NP acompañada de este nivel de autoconciencia, tanto sobre la imposición que se hace en el tiempo de las personas como (más importante) sobre la probabilidad de error. Como sucedió, mi estudiante de doctorado Michael Forbes le envió al autor un informe hermoso y detallado explicando los problemas con su enfoque; el autor agradeció a Michael y (¡creo! :-)) pagó lo prometido.

Entonces sí: para los aficionados que quieren que alguien examine sus pruebas P vs. NP (o un trabajo similar), creo que pagarle a un estudiante graduado unos cientos de dólares es una excelente manera de hacerlo. (Tenga en cuenta que los estudiantes de posgrado son una opción mucho mejor que los profesores: no solo tienen más energía y entusiasmo por esas cosas, sino que también necesitan más dinero). Deseo que más aficionados aprovechen esta opción.

Durante unos meses al final de mi último año de universidad y al comienzo de mi primer año de posgrado, gané $ 60 / hora corrigiendo las pruebas incorrectas de un aficionado del último teorema de Fermat. En este caso, la persona era académica en otro campo, por lo que tenía una comprensión razonable del valor del tiempo experto. Fue una buena experiencia en general, gané mil dólares a la vez que no tenía otras buenas fuentes de ingresos, y aprendió los errores que cometió en varios borradores.

Creo que para las personas que están haciendo un esfuerzo genuino y que están dispuestas a pagar un buen dinero, no debería ser difícil encontrar estudiantes universitarios calificados o jóvenes graduados que necesiten algo de dinero.

Un problema que veo con su sugerencia es que la mayoría de las no pruebas de P vs NP ni siquiera son falsas. En otras palabras, generalmente sufren un fallo de definición o especificación que hace que sea imposible verificarlo como verdadero o demostrar que es falso. Lo remitiré a mi caricatura (¡desvergonzada alerta de autopromoción!) De la interacción típica entre expertos y entusiastas aficionados de P vs NP : es difícil ver cómo la introducción de dinero en esta discusión lo mejoraría.

PD: la caricatura anterior se basa en ver los naufragios en la teoría de la composición: Timothy Chow podría tener más que decir sobre esto, ya que a menudo intenta pacientemente involucrar a esa gente.

Recuerdo que asistí a una conferencia de idiomas alrededor de 1985 donde se realizó el siguiente intercambio:

Orador: Las hojas del árbol son ejemplos de un problema de NP completo, pero son fáciles de resolver a mano.

Yo: Si las instancias son fáciles de resolver, tal vez el problema no sea NP completo.

Ponente: No entiendo.

$ 300 parece muy poco para cobrar. Solo paga una hora o 2 de tiempo. Cualquier prueba de ese corto ya ha sido descartada.

Definitivamente no. No necesitamos otra alternativa académica. Ciertas personas ya han proporcionado esas alternativas, brindando a los investigadores aficionados y profesionales y a la sociedad falsas esperanzas de un futuro de alta tecnología (tengo en mente un lugar en particular, pero prefiero no mencionarlo).

El sistema académico se forjó después de siglos en lo que es. Veo intentos de omitir el sistema de revisión por pares simplemente como "omitir la línea". Si un investigador aficionado no tiene la habilidad de entender por qué su prueba está equivocada, ya sea sola o con algunos comentarios de la revisión, entonces hay una solución simple y es que debe estudiar el tema más a fondo. Es por eso que existen instituciones educativas como las universidades, para certificar el conocimiento de cierta persona. Si esa persona resulta ser un genio que capta el conocimiento del campo al instante, bien, otorgue ese grado lo antes posible. Pero la gran mayoría debe y debe recibir capacitación por su propio bien y por el bien de la sociedad.

¿Qué pensaría si esta línea de negocios se tomara de las matemáticas y se pusiera en medicina u otro campo donde las consecuencias sean más inmediatas? ¿Cuánto tiempo hasta que un hombre de negocios poco confiable a propósito altere los documentos de aficionados para que sean difíciles de revisar o puedan engañar al revisor? Engañar a los clientes-investigadores aficionados está destinado a suceder, como ocurre con todas las empresas que dependen de los conocimientos difíciles de obtener.

Puede ver que mi punto es que hay problemas funcionales incluso antes de profundizar en los detalles técnicos. Y como estoy haciendo un argumento de ingeniería, la "programación" es un buen ejemplo de lo que sucede cuando los aficionados intentan hacer un trabajo serio con poca o ninguna capacitación. Lo último que necesita una comunidad científica es que los medios glorifiquen al próximo "informático teórico autodidacta que desafía los fundamentos de toda la comunidad científica desde su garaje", y mucho menos una ciencia frágil como la nuestra, que aún trata de obtener el reconocimiento. merece.