Beispiele für Pedanterie in TCS

Larry Wasserman hat kürzlich einen Beitrag verfasst, in dem er über die "P-Value-Polizei" spricht. Er macht einen interessanten Punkt (alles Hervorheben von mir) (die Prämisse in Kursivschrift, die ich hinzugefügt habe, und seine Antwort darunter):

Die häufigste Beschwerde ist, dass Physiker und Journalisten die Bedeutung eines p-Wertes falsch erklären. Wenn zum Beispiel der p-Wert 0,000001 ist, sehen wir Aussagen wie „Es gibt eine 99,9999% ige Sicherheit, dass das Signal echt ist.“ Wir fühlen uns dann gezwungen, die Aussage zu korrigieren: Wenn es keinen Effekt gibt, dann besteht die Chance, dass etwas passiert als oder extremer ist 0,000001.

Meinetwegen. Aber ist es wirklich wichtig? Das große Bild ist: Die Beweise für die Wirkung sind überwältigend. Ist es wirklich wichtig, wenn die Formulierung etwas irreführend ist? Ich denke, wir stärken unser Image als Pedanten, wenn wir uns darüber beschweren.

Was mich zum Nachdenken brachte -

Gibt es gute Beispiele für Pedanterie in TCS? Ein solches Beispiel würde bestehen aus

• Eine Behauptung, die allgemein in der populären Presse gemacht wird
• Eine Standardkorrektur, auf die die Leute bestehen
• Das richtige "Gesamtbild", das die Behauptung auch dann erfasst, wenn sie ungenau ist.

wo die Behauptung mathematisch falsch, aber "moralisch richtig" ist und die Korrektur technisch korrekt ist, aber das intuitive Verständnis nicht verändert.

Um die Dinge abzulenken, wäre mein Beispiel:

• Behauptung - NP-vollständige Probleme brauchen exponentiell viel Zeit, um gelöst zu werden
• Korrektur - Nein, wir wissen nur nicht, ob sie in polynomialer Zeit gelöst werden können
• Gesamtbild - NP-vollständige Probleme sind SCHWER

Achtung: Ich weiß, dass es in diesem Forum viele gibt, deren Kopf bei der Vorstellung von Behauptungen explodiert, die falsch, aber "moralisch korrekt" sind :). Denken Sie daran, dass dies Aussagen sind, die sich an die Öffentlichkeit richten (wo ein gewisser Grad an Lizenz erlaubt sein kann), anstatt Aussagen, die in einem Forschungsbericht gemacht wurden.

Hm, es ist schwierig, an Beispiele für Behauptungen über TCS zu denken, die es in die populäre Presse schaffen.

Eine Sache, die ich gelegentlich gesehen habe, ist die Behauptung, dass Factoring bei der Erklärung der Kryptographie NP-hart ist. Dies hängt mit dem weniger harmlosen Fehler zusammen, zu behaupten, Quantencomputer könnten schwierige NP-Probleme lösen, ist aber auf den Kontext der Kryptographie beschränkt. Dies ist ein relativ geringer Fehler. Der Punkt ist nur, dass wir (Benutzer der Kryptographie) zu glauben scheinen, dass es keinen effizienten Algorithmus zur Lösung des Problems gibt. Die speziellen Vermutungen, mit denen wir diese Behauptung rechtfertigen, gehen daneben.

• Behauptung durch Presse: über Dinge, die "exponentiell" wachsen, dh Behauptung von O (k ^ n)

• eigentlich wahr: oft eine konstante Leistung O (n ^ k)

• großes bild: es wächst schnell genug

• Behauptung durch die Presse: Der erste polynomiale Zeitalgorithmus für ein wichtiges praktisches Problem wird zwangsläufig unser Leben verändern, wird nach geschnittenem Brot das zweitbeste sein usw.

Nehmen Sie zum Beispiel einen Presseartikel über den Ellipsoid-Algorithmus aus der Zeit, als er entdeckt wurde (ein guter Bericht über die Geschichte: http://www.springerlink.com/content/vh32532p5048062u/ ). Die Presse behauptete, diese neue große mathematische Entdeckung werde das Leben aller Menschen beeinflussen, TSP lösen (was sie angesichts der geringen Anzahl reisender Verkäufer in der UdSSR als besonders ironisch empfanden!), Krypto auf den Kopf stellen usw.

Dann gibt es AKS, das in einigen Berichten sogar impliziert wurde, Factoring zu lösen, oder zumindest eine Innovation zu sein, die die Branche verändert.

Ich bin mir sicher, dass es noch viele weitere Beispiele gibt.

• Eigentlich stimmt: Polynomialzeit bedeutet nicht praktisch! Beispiel: Ellipsoidalgorithmus, Abtastung aus hochdimensionalen konvexen Körpern. Im schlimmsten Fall bedeutet exponentielle Zeit nicht unpraktisch. Beispiel: Simplex-Algorithmus. Wenn der neue Algorithmus lediglich der erste deterministische Polyzeit-Algorithmus für ein Problem ist, ist dies für die Praxis noch weniger relevant.

• $\log^5 n$

Die populäre Presse erweckt oft den Eindruck, dass der Hauptgrund, wenn nicht der einzige, warum Computer bei immer mehr Aufgaben erfolgreich sind (Kasparov beim Schach schlagen, Jennings bei Jeopardy schlagen usw.), eine erhöhte rohe Verarbeitungsleistung ist. Algorithmische Fortschritte werden normalerweise nicht so hoch gewertet.

Ich bin mir jedoch nicht sicher, ob es "Pedanterie" ist, darauf zu bestehen, dass algorithmischen Fortschritten mehr Gewicht beigemessen wird. Einerseits denke ich, dass diejenigen von uns, die eher theoretisch geneigt sind, manchmal die Wichtigkeit algorithmischer Fortschritte übertreiben und nur widerwillig die Wichtigkeit erhöhter Verarbeitungsleistung zugeben können. Andererseits denke ich, dass die Öffentlichkeit besser über die Rolle theoretischer Fortschritte bei der Lösung praktischer Probleme informiert werden sollte.

Scott Aaronson, obwohl er eine der führenden Autoritäten ist, scheint die Medien regelmäßig vor Gericht zu stellen, weil sie die Haare nicht richtig spalten. zB seine kürzlich erschienene Kolumne im NYT-Artikel "Quantum Computing verspricht neue Erkenntnisse, nicht nur Supermaschinen" [kursiv gedruckt]

Die populärsten Schriftsteller bemühen sich, die Mathematik in zeitungsfreundliche Metaphern zu verwandeln, und beschreiben einen Quantencomputer als eine magische Maschine, die jede mögliche Antwort parallel verarbeiten kann, anstatt sie einzeln auszuprobieren. Angeblich könnte dies der Fall sein, da ein Quantencomputer im Gegensatz zu heutigen Computern, die Bits manipulieren, Quantenbits oder Qubits manipulieren würde, die gleichzeitig 0 und 1 sein können.

Aber das ist eine grobe Methode, um zu visualisieren, was ein Quantencomputer tut, und verpasst den wichtigsten Teil der Geschichte. Wenn Sie die Ausgabe eines Quantencomputers messen, sehen Sie nur eine einzelne, zufällige Antwort - nicht eine Auflistung aller möglichen Antworten. Wenn Sie nur eine zufällige Antwort hätten wollen, hätten Sie sich natürlich auch eine aussuchen können, und das mit viel weniger Aufwand.

Dennoch ist die Metapher einer Quantencomputerverarbeitung, die Antworten parallel verarbeitet, weit verbreitet und eine sinnvolle konzeptionelle Vereinfachung des QM-Computing, auf die in vielen QM-Computing-Lehrbüchern Bezug genommen wird. Es gibt wahrscheinlich andere Beispiele aus der QM-Theorie / Computing.

TCS und andere theoretische Forschungen haben eine natürliche Spannung in der Kommunikation mit der Öffentlichkeit / den Medien, da sie manchmal dazu neigen, kritische Unterscheidungen / Konzepte als Teil einer rigorosen Ausbildung hervorzuheben, die für Laien nicht bekannt oder entscheidend sind. mit anderen Worten, in vielen Fällen arbeitet die Forschungstheorie gegen verschiedene konzeptionelle "Gesamtbild" -Vereinfachungen, die für Laien legitim sind.