Les experts du TCS devraient-ils facturer de l'argent pour lire les preuves que P! = NP?

Il est bien connu qu'il y a des tonnes d'amateurs - moi y compris - qui s'intéressent au problème P vs NP. Il y a aussi beaucoup d'amateurs - moi y compris toujours - qui ont tenté de résoudre le problème.

Un problème dont je pense que la communauté TCS souffre est un rapport relativement élevé entre amateur et expert; cela conduit les experts à être inondés de preuves que P! = NP, et j'ai lu qu'ils sont frustrés et dépassés, tout naturellement, par cette situation. Oded Goldreich a écrit sur cette question et a indiqué son propre refus de vérifier les preuves.

En même temps, parlant du point de vue d'un amateur, je peux affirmer qu'il y a peu de choses plus frustrantes pour les amateurs de TCS de niveau non expert de tout niveau que de générer une preuve qui semble juste, mais qui manque des deux la capacité de trouver l'erreur dans la preuve vous-même et la possibilité de parler à toute personne qui peut repérer des erreurs dans votre preuve. Récemment, RJ Lipton a écrit sur le problème des amateurs qui essaient d'être pris au sérieux.

J'ai une proposition pour résoudre ce problème, et ma question est de savoir si les autres le jugent raisonnable ou s'il y a des problèmes.

Je pense que les experts devraient facturer une somme d'argent importante mais raisonnable (disons, 200 - 300 USD) en échange d'accepter de lire les épreuves en détail et d'y trouver des erreurs spécifiques. Cela accomplirait trois choses:

1. Les amateurs auraient un moyen clair de faire évaluer et prendre au sérieux leurs épreuves.
2. Les experts seraient rémunérés pour leur temps et leur énergie dépensés.
3. Il y aurait un coût considérablement élevé imposé à la vérification de la preuve que le nombre de preuves que les amateurs soumettent diminuerait considérablement.

Encore une fois, ma question est de savoir s'il s'agit ou non d'une proposition raisonnable. De toute évidence, je n'ai pas la capacité de faire adopter par des experts ce que je suggère; cependant, j'espère que les experts liront ce que j'ai écrit et décideront que c'est raisonnable.

Permettez-moi de répondre à votre suggestion par une contre-suggestion: pourquoi n'essayez-vous pas de créer une entreprise en agissant en tant qu'intermédiaire entre amateurs et experts? Les amateurs paient pour faire évaluer leurs épreuves. Vous trouvez un expert et payez l'expert pour évaluer la preuve, en prélevant une somme d'argent pour votre rôle d'intermédiaire. Essayer de diriger une telle entreprise est le moyen le plus fiable de savoir si votre idée est réalisable.

J'ai une "expérience du monde réel" dans cette industrie naissante (et non, je ne parle pas de mon offre de 200 000 $ à Deolalikar :-))

En janvier, un développeur de logiciel m'a envoyé un e-mail indiquant qu'il avait une tentative de preuve de P ≠ NP, et que même s'il était presque sûr qu'il y avait une erreur, il ne l'avait pas trouvée. Il m'a demandé si je connaissais des étudiants diplômés qui seraient prêts à trouver l'erreur pour lui en échange de quelques centaines de dollars.

Pour vous donner un peu de contexte: j'obtiens une preuve de P ≠ NP ou P = NP dans ma boîte de réception environ une fois par mois. Beaucoup de ces courriels vont à une longue liste de théoriciens de la complexité (Cook, Karp, Fortnow, Sipser ...); ils incluent souvent des ruminations religieuses ou métaphysiques ainsi que des indices sombres sur les complots académiques. (Dans un cas, il y a eu des menaces de mort graphiques contre moi, ce qui m'a amené à contacter la police.) aucun d'entre eux ne reconnaît la possibilité que la preuve soit fausse ou que l'auteur ait mal compris la question. Et quand, à la fin de mes études, j'ai essayé de correspondre avec les auteurs, j'ai trouvé que tous croyaient ardemment à la maxime de Churchill "ne jamais, jamais, jamais, jamais abandonner".

Donc, la demande du développeur du logiciel m'a donc vraiment impressionné! C'était la première fois que je voyais une preuve P ≠ NP accompagnée de ce niveau de conscience de soi --- à la fois sur l'imposition faite au temps des gens et (plus important) sur la probabilité d'erreur. En l'occurrence, mon étudiant au doctorat Michael Forbes a envoyé à l'auteur un beau rapport détaillé expliquant les problèmes de son approche; l'auteur a remercié Michael et (je pense! :-)) a payé comme promis.

Alors oui: pour les amateurs qui veulent que quelqu'un examine leurs preuves P vs NP (ou un travail similaire), je pense que payer quelques centaines de dollars à un étudiant diplômé est une excellente façon de procéder. (Notez que les étudiants diplômés sont un bien meilleur choix que les professeurs: non seulement ils ont plus d'énergie et d'enthousiasme pour de telles choses, ils ont également besoin de plus d'argent.) Je souhaite que plus d'amateurs se prévalent de cette option.

Pendant quelques mois à la fin de ma dernière année de collège et au début de ma première année d'études supérieures, j'ai gagné 60 $ / heure en corrigeant les preuves incorrectes d'un amateur du dernier théorème de Fermat. Dans ce cas, la personne était un universitaire dans un autre domaine, donc elle avait une compréhension raisonnable de la valeur du temps d'expert. C'était une bonne expérience tout autour, j'ai gagné mille dollars à une époque où je n'avais pas d'autres bonnes sources de revenus, et il a appris les erreurs qu'il a commises dans plusieurs ébauches.

Je pense que pour les gens qui font un véritable effort et qui sont prêts à payer beaucoup d'argent, il ne devrait pas être difficile de trouver des étudiants de premier cycle qualifiés ou de jeunes étudiants diplômés qui ont besoin d'argent.

Un problème que je vois avec votre suggestion est que la plupart des non-preuves P vs NP ne sont même pas fausses. En d'autres termes, ils souffrent généralement d'un échec de définition ou de spécification qui les rend impossibles à vérifier comme vrais ou à prouver qu'ils sont faux. Je vais vous renvoyer à ma (alerte d'auto-promotion éhontée!) Caricature de l'interaction typique entre les experts et l'amateur P vs NP amateur : il est difficile de voir comment l'introduction d'argent dans cette discussion pourrait l'améliorer.

ps la caricature ci-dessus est basée sur l'observation d'épaves de train sur la théorie de la maquette: Timothy Chow pourrait avoir plus à dire à ce sujet, car il essaie souvent patiemment d'engager de telles personnes.

Je me souviens être allé à une conférence linguistique vers 1985 où l'échange suivant a eu lieu:

Conférencier: Les feuilles de l'arbre sont des exemples d'un problème NP-complet, mais sont faciles à résoudre à la main.

Moi: Si les instances sont faciles à résoudre, le problème n'est peut-être pas complet.

Conférencier: Je ne comprends pas.

300 $ semble trop peu cher à facturer. Il ne paie qu'une heure ou deux. Toute preuve de ce court a déjà été écartée.

Définitivement pas. Nous n'avons pas encore besoin d'une autre alternative universitaire. Certaines personnes ont déjà fourni ces alternatives, donnant aux chercheurs amateurs et professionnels et à la société de faux espoirs d'un avenir high-tech (j'ai un lieu particulier en tête mais je préfère ne pas le mentionner).

Le système universitaire a été forgé après des siècles en ce qu'il est. Je vois les tentatives de sauter le système d'examen par les pairs comme simplement "sauter la ligne". Si un chercheur amateur n'a pas les compétences nécessaires pour comprendre pourquoi sa preuve est fausse, seule ou avec quelques commentaires de révision, alors il existe une solution simple et c'est qu'elle doit étudier le sujet en question plus dur. C'est pourquoi des établissements d'enseignement tels que les universités existent, pour certifier les connaissances d'une certaine personne. Si cette personne se trouve être un génie qui saisit instantanément la connaissance du domaine, d'accord, décernez ce diplôme dès que possible. Mais la grande majorité doit et doit suivre une formation pour elle-même et pour la société.

Que penseriez-vous si cette branche d'activité était empruntée aux mathématiques et mise en médecine ou dans un autre domaine où les conséquences sont plus immédiates? Combien de temps jusqu'à ce qu'un homme d'affaires indigne de confiance modifie délibérément les journaux amateurs afin qu'ils soient difficiles à réviser ou puissent tromper le critique? Tromper les chercheurs amateurs-clients est inévitable, comme pour toutes les entreprises qui comptent sur des informations difficiles à obtenir.

Vous pouvez voir que mon point est qu'il y a des problèmes fonctionnels avant même de plonger dans les détails techniques. Et puisque je fais un argument d'ingénierie, la "programmation" est un bon exemple de ce qui se passe lorsque des amateurs essaient de faire un travail sérieux avec peu ou pas de formation. La dernière chose dont toute communauté scientifique a besoin, ce sont les médias qui glorifient le prochain "informaticien théorique autodidacte qui remet en question les fondements de toute la communauté scientifique depuis son garage", sans parler d'une science fragile comme la nôtre, qui essaie toujours de la faire reconnaître. mérite.