Exemples de pédanterie dans TCS

Larry Wasserman a récemment publié un article dans lequel il parle de la "police p-value". Il fait un point intéressant (tout l'accent est mis sur moi) (la prémisse en italique que j'ai ajoutée et sa réponse ci-dessous):

La plainte la plus courante est que les physiciens et les journalistes expliquent incorrectement la signification d'une valeur de p. Par exemple, si la valeur de p est 0,000001, alors nous verrons des déclarations comme «il y a une confiance de 99,9999% que le signal est réel». Nous nous sentons alors obligés de corriger la déclaration: s'il n'y a pas d'effet, alors la chance de quelque chose ou plus extrême est 0,000001.

C'est suffisant. Mais est-ce que c'est vraiment important? La vue d'ensemble est la suivante: les preuves de l'effet sont écrasantes. Est-ce vraiment important si le libellé est un peu trompeur? Je pense que nous renforçons notre image de pédants si nous nous en plaignons.

Ce qui m'a fait réfléchir -

Y a-t-il de bons exemples de pédanterie dans TCS? Un tel exemple consisterait en

• Une affirmation qui est communément faite dans la presse populaire
• Une correction standard que les gens insistent pour faire
• La "vue d'ensemble" correcte que la revendication capture, même si elle est imprécise.

où l'affirmation est mathématiquement erronée mais "moralement juste" et la correction est techniquement correcte mais ne change pas la compréhension intuitive.

Pour commencer, mon exemple serait:

• Allégation - Les problèmes NP-complets prennent un temps exponentiel à résoudre
• Correction - Non, en fait, nous ne savons tout simplement pas s'ils peuvent être résolus en temps polynomial
• Vue d'ensemble - Les problèmes NP-complets sont DIFFICILES

Attention: je sais qu'il y en a beaucoup sur ce forum dont la tête va exploser à l'idée de revendications fausses mais "moralement correctes" :). N'oubliez pas que ce sont des déclarations destinées au public (où un certain degré de licence peut être autorisé), plutôt que des déclarations faites dans un document de recherche.

Hm, il est difficile de penser à des exemples de réclamations sur TCS qui parviennent à la presse populaire.

Une chose que j'ai vue à l'occasion est l'affirmation selon laquelle l'affacturage est NP-difficile, lors de l'explication de la cryptographie. Ceci est lié à l'erreur moins inoffensive de prétendre que les ordinateurs quantiques peuvent résoudre des problèmes difficiles de NP, mais limité au contexte de la cryptographie, il s'agit d'une erreur relativement légère. Le fait est que nous (utilisateurs de la cryptographie) semblons croire qu'il n'y a pas d'algorithme efficace pour résoudre le problème. Les conjectures particulières que nous utilisons pour justifier cette affirmation sont d'ailleurs pertinentes.

• revendication par la presse: à propos de choses qui croissent "exponentiellement", c'est-à-dire la revendication de O (k ^ n)

• en fait vrai: souvent, une puissance constante O (n ^ k)

• vue d'ensemble: ça pousse assez vite, d'accord

• Revendication par la presse: le premier algorithme de temps polynomial pour un problème pratique important changera nécessairement nos vies, sera la prochaine meilleure chose après le pain tranché, etc.

Pour des exemples, prenez n'importe quel article de presse sur l'algorithme ellipsoïde du moment où il a été découvert (grand compte de l'histoire: http://www.springerlink.com/content/vh32532p5048062u/ ). La presse a affirmé que cette nouvelle grande découverte mathématique affecterait la vie de tout le monde, résoudrait le TSP (qu'ils ont trouvé particulièrement ironique étant donné le peu de vendeurs itinérants en URSS!), Bouleverserait la crypto, etc.

Ensuite, il y a l'AKS, qui dans certains rapports a même été impliquée pour résoudre l'affacturage ... ou du moins pour être une innovation qui change l'industrie.

Je suis sûr qu'il existe de nombreux autres exemples.

• En réalité, le temps polynomial ne signifie pas pratique! Exemple: algorithme ellipsoïde, échantillonnage à partir de corps convexes de grande dimension. Le temps exponentiel dans le pire des cas ne signifie pas impraticable. Exemple concret: algorithme simplex. Lorsque le nouvel algorithme n'est que le premier algorithme déterministe de polytime pour un problème, cela a encore moins de pertinence pour la pratique.

• $\log^5 n$

La presse populaire donne souvent l'impression que la principale, sinon la seule, raison pour laquelle les ordinateurs réussissent de plus en plus de tâches (battre Kasparov aux échecs, battre Jennings à Jeopardy, etc.) est l'augmentation de la puissance de traitement brute. Les avancées algorithmiques n'ont généralement pas autant de crédit.

Cependant, je suis ambivalent quant à savoir si insister pour que les avancées algorithmiques reçoivent plus de poids soit de la «pédanterie». D'une part, je pense que ceux d'entre nous qui sont plus enclins à la théorie peuvent parfois surestimer l'importance des avancées algorithmiques et admettre à contrecœur l'importance d'une puissance de traitement accrue. D'un autre côté, je pense que le public devrait être mieux informé du rôle des avancées théoriques dans la résolution des problèmes pratiques.

Scott Aaronson, tout en étant une autorité de premier plan, semble régulièrement reprocher aux médias de ne pas se coiffer avec précision. par exemple sa récente chronique dans l'article du NYT "L'informatique quantique promet de nouvelles perspectives, pas seulement des supermachines" [italiques ajoutés]

Luttant vers un chausse-pied qui transforme les mathématiques en métaphores adaptées aux journaux, la plupart des écrivains populaires décrivent un ordinateur quantique comme une machine magique qui pourrait traiter toutes les réponses possibles en parallèle, plutôt que de les essayer une par une. Soi-disant, cela pourrait le faire parce que, contrairement aux ordinateurs d'aujourd'hui qui manipulent les bits, un ordinateur quantique manipulerait les bits quantiques, ou qubits, qui peuvent être 0 et 1 simultanément.

Mais c'est une façon grossière de visualiser ce que fait un ordinateur quantique, et il manque la partie la plus importante de l'histoire. Lorsque vous mesurez la sortie d'un ordinateur quantique, vous ne voyez qu'une seule réponse aléatoire - pas une liste de toutes les réponses possibles. Bien sûr, si vous aviez simplement voulu une réponse aléatoire, vous auriez pu en choisir une vous-même, avec beaucoup moins de difficultés.

Pourtant, la métaphore d'un ordinateur quantique traitant des réponses en parallèle est répandue et une simplification conceptuelle raisonnable de l'informatique QM, et mentionnée dans de nombreux manuels d'informatique QM. il y a probablement d'autres exemples de la théorie / informatique QM.

il existe une tension naturelle dans le TCS et d'autres recherches théoriques dans la communication avec le public / les médias, car elle tend parfois à mettre l'accent sur les distinctions / concepts critiques dans le cadre d'une formation rigoureuse qui n'est pas connue ou cruciale pour les profanes. en d'autres termes, dans de nombreux cas, la théorie de la recherche va à l'encontre de diverses simplifications conceptuelles «d'ensemble» qui sont légitimes pour les profanes.