Sollten TCS-Experten Geld verlangen, um Beweise zu lesen, dass P! = NP ist?

Es ist bekannt, dass es Unmengen von Amateuren gibt - ich selbst eingeschlossen -, die sich für das P vs. NP-Problem interessieren. Es gibt auch viele Amateure - ich bin immer noch dabei -, die versucht haben, das Problem zu lösen.

Ein Problem, unter dem die TCS-Community zu leiden hat, ist meines Erachtens ein relativ hohes Verhältnis zwischen Amateur und Experte. Dies führt dazu, dass Experten mit Beweisen überflutet werden, dass P! = NP, und ich habe gelesen, dass sie von dieser Situation frustriert und verständlicherweise überfordert sind. Oded Goldreich hat geschrieben zu diesem Thema, und zeigte seine eigene Ablehnung Beweise zu prüfen.

Gleichzeitig kann ich aus der Sicht eines Amateurs behaupten, dass es für TCS-Enthusiasten ohne Expertenwissen kaum frustrierendere Dinge gibt, als einen Beweis zu erbringen, der einfach richtig scheint , aber beides fehlt die Fähigkeit, den Fehler im Proof selbst zu finden, und die Fähigkeit, mit jedem zu sprechen, der Fehler in Ihrem Proof erkennen kann. Vor kurzem RJ Lipton schrieb über das Problem der Amateure , die ernst genommen zu bekommen versuchen.

Ich habe einen Vorschlag zur Lösung dieses Problems und meine Frage ist, ob andere dies für sinnvoll halten oder ob es Probleme damit gibt.

Ich denke, Experten sollten einen erheblichen, aber angemessenen Geldbetrag (z. B. 200 - 300 USD) verlangen, um zuzustimmen, Beweise im Detail zu lesen und darin bestimmte Fehler zu finden. Dies würde drei Dinge bewirken:

1. Amateure hätten einen klaren Weg, ihre Beweise beurteilen und ernst nehmen zu lassen.
2. Experten würden für ihren Zeit- und Energieaufwand entschädigt.
3. Die Überprüfung von Beweisen wäre mit einem erheblichen Kostenaufwand verbunden, da die Anzahl der von Amateuren eingereichten Beweise drastisch sinken würde.

Auch hier ist meine Frage, ob dies ein vernünftiger Vorschlag ist oder nicht. Offensichtlich bin ich nicht in der Lage, Experten zu veranlassen, das zu übernehmen, was ich vorschlage. Ich hoffe jedoch, dass Experten lesen, was ich geschrieben habe, und entscheiden, dass es angemessen ist.

Lassen Sie mich auf Ihren Vorschlag mit einem Gegenvorschlag antworten: Warum versuchen Sie nicht, ein Unternehmen zu gründen, das als Vermittler zwischen Amateuren und Experten fungiert? Amateure zahlen, um ihre Beweise bewerten zu lassen. Sie suchen einen Experten und bezahlen den Experten, um den Beweis zu beurteilen, indem Sie das Geld für Ihre Vermittlerrolle kürzen. Der Versuch, ein solches Geschäft zu führen, ist die zuverlässigste Methode, um herauszufinden, ob Ihre Idee realisierbar ist.

Ich habe einige "echte Erfahrungen" in dieser aufstrebenden Branche (und nein, ich spreche nicht über mein 200.000-Dollar-Angebot an Deolalikar :-))

Im Januar schickte mir ein Softwareentwickler eine E-Mail, dass er versucht habe, P ≠ NP zu beweisen, und dass er, obwohl er fast sicher war, dass ein Fehler vorliegt, ihn nicht finden konnte. Er fragte, ob ich irgendwelche Studenten kenne, die bereit wären, für ein paar hundert Dollar den Fehler für ihn zu finden.

Um Ihnen einen Anhaltspunkt zu geben: Ich bekomme ungefähr einmal im Monat einen Nachweis von entweder P ≠ NP oder P = NP in meinem Posteingang. Viele dieser E-Mails gehen an eine lange Liste von Komplexitätstheoretikern (Cook, Karp, Fortnow, Sipser ...); sie enthalten oft religiöse oder metaphysische Überlegungen sowie dunkle Hinweise auf akademische Verschwörungen. (In einem Fall gab es grafische Morddrohungen gegen mich, die dazu führten, dass ich die Polizei kontaktierte.) Praktisch keiner von ihnen erkennt die Möglichkeit an, dass der Beweis falsch sein könnte oder dass der Autor die Frage falsch verstanden hat. Und als ich in der Grundschule versuchte, mit den Autoren zu korrespondieren, stellte ich fest, dass sie alle leidenschaftlich an Churchills Maxime "niemals, niemals, niemals, niemals aufgeben" glaubten.

Die Anfrage des Softwareentwicklers hat mich wirklich beeindruckt! Dies war das erste Mal, dass ich einen P ≠ NP-Beweis gesehen habe, der von dieser Ebene des Selbstbewusstseins begleitet war - sowohl über die Auferlegung der Zeit der Menschen als auch (was noch wichtiger ist) über die Wahrscheinlichkeit von Fehlern. Zufällig sandte mein Doktorand Michael Forbes dem Autor einen schönen, detaillierten Bericht, in dem er die Probleme mit seiner Herangehensweise erläuterte. Der Autor bedankte sich bei Michael und zahlte wie versprochen.

Also ja: Für Amateure, die möchten, dass jemand ihre P-gegen-NP-Beweise (oder ähnliche Arbeiten) überprüft, ist es ein guter Weg, einem Doktoranden ein paar Hundert Dollar zu zahlen. (Beachten Sie, dass Doktoranden eine viel bessere Wahl sind als Professoren: Sie haben nicht nur mehr Energie und Begeisterung für solche Dinge, sie brauchen auch mehr Geld.) Ich wünsche mir, dass mehr Amateure von dieser Möglichkeit Gebrauch machen.

Am Ende meines letzten Studienjahres und zu Beginn meines ersten Studienjahres verdiente ich ein paar Monate lang 60 US-Dollar pro Stunde, um die falschen Beweise eines Amateurs für Fermats letzten Satz zu korrigieren. In diesem Fall war die Person ein Akademiker auf einem anderen Gebiet, sodass sie den Wert der Expertenzeit gut verstand. Es war eine gute Erfahrung, ich verdiente tausend Dollar zu einer Zeit, in der ich keine anderen guten Einnahmequellen hatte, und er erfuhr, welche Fehler er in mehreren Entwürfen gemacht hatte.

Ich denke, für Leute, die sich wirklich anstrengen und bereit sind, gutes Geld zu zahlen, sollte es nicht schwer sein, qualifizierte Studenten oder junge Doktoranden zu finden, die etwas Geld brauchen.

Ein Problem, das ich mit Ihrem Vorschlag sehe, ist, dass die meisten P-gegen-NP-Nichtbeweise nicht einmal falsch sind. Mit anderen Worten, sie leiden normalerweise unter einem Definitions- oder Spezifikationsfehler, der es ihnen unmöglich macht, entweder als wahr zu verifizieren oder sich als falsch zu erweisen. Ich verweise Sie auf meine (schamlose Selbst-Promotion-Warnung!) Karikatur der typischen Interaktion zwischen Experten und dem Amateur-P-gegen-NP-Enthusiasten : Es ist schwer zu sehen, wie die Einführung von Geld in diese Diskussion diese verbessern würde.

ps die oben Karikatur basiert auf trainwrecks auf comp.theory beobachten: Timothy Chow könnte mehr haben , darüber zu sagen, da er oft geduldig Versuche , solches Volk zu engagieren.

Ich erinnere mich an eine Sprachkonferenz um 1985, bei der folgender Austausch stattfand:

Sprecher: Die Blätter des Baumes sind Beispiele für ein NP-vollständiges Problem, aber einfach von Hand zu lösen.

Me: Wenn die Instanzen leicht zu lösen sind, ist das Problem möglicherweise nicht NP-vollständig.

Sprecher: Ich verstehe nicht.

300 Dollar scheinen zu wenig zu sein, um sie in Rechnung zu stellen. Es zahlt sich nur eine oder zwei Stunden aus. Ein solcher Nachweis ist bereits ausgeschlossen.

Definitiv nicht. Wir brauchen keine weitere akademische Alternative. Einige Leute haben diese Alternativen bereits angeboten und damit sowohl Laien- als auch Berufsforschern und der Gesellschaft falsche Hoffnungen auf eine Hightech-Zukunft gemacht (ich habe einen bestimmten Veranstaltungsort im Auge, möchte ihn aber lieber nicht erwähnen).

Das akademische System wurde nach Jahrhunderten zu dem geschmiedet, was es ist. Ich sehe Versuche, das Peer-Review-System zu überspringen, einfach als "Überspringen der Leitung". Wenn eine Amateurforscherin nicht die Fähigkeit hat, zu verstehen, warum ihr Beweis falsch ist, entweder allein oder mit einigen Kommentaren aus der Überprüfung, dann gibt es eine einfache Lösung, und das heißt, sie muss das vorliegende Thema härter studieren. Aus diesem Grund existieren Bildungseinrichtungen wie Universitäten, um das Wissen einer bestimmten Person zu zertifizieren. Wenn diese Person zufällig ein Genie ist, das das Wissen des Gebiets sofort erfasst, gut, vergeben Sie diesen Grad so bald wie möglich. Aber die überwiegende Mehrheit muss und sollte sich um ihrer selbst und der Gesellschaft willen ausbilden lassen.

Was würden Sie denken, wenn dieser Geschäftszweig aus der Mathematik übernommen und in die Medizin oder ein anderes Gebiet verlegt würde, in dem die Konsequenzen unmittelbarer sind? Wie lange dauert es, bis ein nicht vertrauenswürdiger Geschäftsmann die Amateurpapiere absichtlich so verändert, dass sie schwer zu überprüfen sind oder den Rezensenten zum Narren halten können? Wie bei allen Unternehmen, die auf schwer zu beschaffendes Wissen angewiesen sind, ist es unumgänglich, Kunden und Amateurforscher zu täuschen.

Sie können sehen, dass es meiner Meinung nach funktionelle Probleme gibt, bevor ich mich mit den technischen Details befasse. Und da ich ein technisches Argument vorbringe, ist "Programmieren" ein gutes Beispiel dafür, was passiert, wenn Amateure versuchen, mit wenig oder ohne Training ernsthafte Arbeit zu leisten. Das Letzte, was eine wissenschaftliche Gemeinschaft braucht, sind die Medien, die den nächsten "autodidaktischen theoretischen Informatiker verherrlichen, der die Grundlagen der gesamten wissenschaftlichen Gemeinschaft aus seiner Garage heraus in Frage stellt", geschweige denn eine fragile Wissenschaft wie unsere, die immer noch versucht, die Anerkennung zu erlangen verdient.