Exemplos de pediatria no TCS

Larry Wasserman tem um post recente, onde fala sobre a "polícia de valor p". Ele faz uma observação interessante (toda a ênfase é minha) (a premissa em itálico que acrescentei e sua resposta abaixo):

A queixa mais comum é que físicos e jornalistas explicam o significado de um valor-p incorretamente. Por exemplo, se o valor-p for 0,000001, veremos declarações como "existe uma confiança de 99,9999% de que o sinal é real." como ou mais extremo é 0,000001.

Justo. Mas isso realmente importa? O quadro geral é: a evidência para o efeito é esmagadora. Realmente importa se o texto é um pouco enganador? Acho que reforçamos nossa imagem de pedantes se reclamarmos disso.

O que me fez pensar -

Existem bons exemplos de pediatria no TCS? Esse exemplo consistiria em

• Uma reivindicação que é comumente feita na imprensa popular
• Uma correção padrão que as pessoas insistem em fazer
• O "quadro geral" correto que a reivindicação captura mesmo sendo impreciso.

onde a afirmação é matematicamente errada, mas "moralmente correta" e a correção é tecnicamente correta, mas não altera o entendimento intuitivo.

Para liderar, meu exemplo seria:

• Reivindicação - problemas completos de NP levam um tempo exponencial para resolver
• Correção - Não, de fato, simplesmente não sabemos se eles podem ser resolvidos em tempo polinomial
• Quadro geral - problemas NP-completos são DIFÍCEIS

Cuidado: Eu sei que há muitos neste fórum cuja cabeça explodirá com a ideia de afirmações erradas, mas "moralmente corretas" :). Lembre-se de que são declarações direcionadas ao público (onde algum grau de licença pode ser permitido), em vez de declarações feitas em um trabalho de pesquisa.

Hm, é difícil até pensar em exemplos de afirmações sobre o TCS que chegam à imprensa popular.

Uma coisa que tenho visto ocasionalmente é a afirmação de que o fatoração é difícil para NP, ao explicar a criptografia. Isso está relacionado ao erro menos inócuo de afirmar que computadores quânticos podem resolver problemas difíceis de NP, mas restrito ao contexto de criptografia, esse é um erro relativamente leve. O ponto é apenas que nós (usuários de criptografia) parecemos acreditar que não há algoritmo eficiente para resolver o problema. As conjecturas particulares que usamos para justificar essa afirmação estão além do ponto.

• reivindicação pela imprensa: sobre coisas que crescem "exponencialmente", isto é, reivindicação de O (k ^ n)

• na verdade verdade: muitas vezes, uma potência constante O (n ^ k)

• quadro geral: cresce rápido o suficiente, tudo bem

• Reivindicação pela imprensa: o primeiro algoritmo de tempo polinomial para um importante problema prático necessariamente mudará nossas vidas, será a próxima melhor coisa depois de fatias de pão, etc.

Por exemplo, pegue qualquer artigo de imprensa sobre o algoritmo elipsóide desde o momento em que foi descoberto (excelente relato da história: http://www.springerlink.com/content/vh32532p5048062u/ ). A imprensa afirmou que esta nova grande descoberta matemática afetará a vida de todos, resolverá o TSP (o que eles acharam especialmente irônico, dado o número de vendedores ambulantes que existiam na URSS!), Vire a criptografia de cabeça para baixo etc.

Depois, há a AKS, que em alguns relatórios foi até implícita para resolver a fatoração ... ou pelo menos para ser uma inovação que muda o setor.

Estou certo de que existem muitos outros exemplos.

• Na verdade, o tempo polinomial não significa prático! Caso em questão: algoritmo elipsóide, amostragem de corpos convexos de alta dimensão. O pior momento exponencial não significa impraticável. Caso em questão: algoritmo simplex. Quando o novo algoritmo é meramente o primeiro algoritmo determinístico de politempo para um problema, isso tem ainda menos relevância para a prática.

• $\log^5 n$

A imprensa popular costuma dar a impressão de que a principal, senão a única, razão pela qual os computadores estão conseguindo cada vez mais tarefas (derrotar Kasparov no xadrez, derrotar Jennings no Jeopardy etc.) é aumentar o poder de processamento bruto. Os avanços algorítmicos normalmente não recebem tanto crédito.

No entanto, sou ambivalente sobre se insistir em que os avanços algorítmicos recebam mais peso seja "pedantismo". Por um lado, acho que aqueles que são mais inclinados teoricamente às vezes podem exagerar a importância dos avanços algorítmicos e admitir de má vontade a importância do aumento do poder de processamento. Por outro lado, acho que o público deveria estar mais bem informado sobre o papel dos avanços teóricos na solução de problemas práticos.

Scott Aaronson, embora seja uma das principais autoridades, parece levar a mídia regularmente a se encarregar de não cortar os cabelos com precisão. por exemplo, sua recente coluna no artigo do NYT "A computação quântica promete novas idéias, não apenas supermáquinas" [itálico adicionado]

Lutando para calçar essa matemática em metáforas amigas dos jornais, os escritores mais populares descrevem um computador quântico como uma máquina mágica que poderia processar todas as respostas possíveis em paralelo, em vez de experimentá-las uma por vez. Supostamente, isso poderia ser feito porque, diferentemente dos computadores atuais que manipulam bits, um computador quântico manipularia bits quânticos, ou qubits, que podem ser 0 e 1 simultaneamente.

Mas essa é uma maneira grosseira de visualizar o que um computador quântico faz e perde a parte mais importante da história. Quando você mede a saída de um computador quântico, vê apenas uma única resposta aleatória - não uma lista de todas as respostas possíveis. Obviamente, se você quisesse apenas uma resposta aleatória, poderia ter escolhido uma, com muito menos problemas.

no entanto, a metáfora de um processamento quântico de respostas computadorizadas em paralelo é generalizada e uma simplificação conceitual razoável da computação QM, e mencionada em muitos livros didáticos de computação QM. provavelmente existem outros exemplos da teoria / computação de QM.

existe uma tensão natural no TCS e em outras pesquisas teóricas na comunicação com o público / mídia, porque às vezes tende a enfatizar distinções / conceitos críticos como parte de um treinamento rigoroso que não é conhecido ou crucial para os leigos. em outras palavras, em muitos casos, a teoria da pesquisa trabalha contra várias simplificações conceituais do "quadro geral" que são legítimas para os leigos.