Os especialistas em TCS deveriam cobrar dinheiro para ler as provas de que P! = NP?

É sabido que existem muitos amadores - inclusive eu - que estão interessados ​​no problema P vs. NP. Também existem muitos especialistas - inclusive eu - que tentaram resolver o problema.

Um problema que eu acho que a comunidade do TCS sofre é uma proporção relativamente alta de amador-especialista / especialista; isso leva os especialistas a serem inundados com provas de que P! = NP, e eu li que eles estão frustrados e sobrecarregados, de maneira bastante compreensível, por essa situação. Oded Goldreich escreveu sobre esta questão e indicou sua própria recusa em verificar as provas.

Ao mesmo tempo, falando do ponto de vista de um amador, posso afirmar que há poucas coisas mais frustrantes para os entusiastas do TCS de nível não especializado de qualquer nível de habilidade do que gerar uma prova que pareça certa, mas sem as duas a capacidade de encontrar o erro na prova e a capacidade de conversar com qualquer pessoa que possa detectar erros na prova. Recentemente, RJ Lipton escreveu sobre o problema de amadores que tentam ser levados a sério.

Tenho uma proposta para resolver esse problema, e minha pergunta é se outras pessoas acham isso razoável ou se há problemas com ele.

Eu acho que os especialistas deveriam cobrar uma quantia significativa, mas razoável, em dinheiro (digamos, 200 a 300 dólares) em troca de concordar em ler as provas em detalhes e encontrar erros específicos nelas. Isso faria três coisas:

1. Os amadores teriam uma maneira clara de avaliar e levar suas provas a sério.
2. Os especialistas seriam compensados ​​pelo tempo e energia gastos.
3. Haveria um custo significativamente alto imposto na verificação de provas de que o número de provas enviadas por amadores diminuiria drasticamente.

Novamente, minha pergunta é se essa é uma proposta razoável ou não. Obviamente, não tenho capacidade de fazer com que especialistas adotem o que sugiro; no entanto, espero que os especialistas leiam o que escrevi e decidam que é razoável.

Deixe-me responder à sua sugestão com uma contra-sugestão: Por que você não tenta montar um negócio, agindo como intermediário entre amadores e especialistas? Os amadores pagam para que suas provas sejam avaliadas. Você encontra um especialista e paga o especialista para avaliar a prova, gastando uma parte do dinheiro para o seu papel de intermediário. Tentar administrar um negócio desses é a maneira mais confiável de descobrir se sua ideia é viável.

Tenho alguma "experiência do mundo real" nesse setor nascente (e não, não estou falando da minha oferta de US $ 200.000 para Deolalikar :-))

Em janeiro, um desenvolvedor de software me enviou um e-mail informando que havia tentado uma prova de P ≠ NP e que, embora tivesse quase certeza de que havia um erro, não conseguiu encontrá-lo. Ele perguntou se eu conhecia algum estudante de graduação que estaria disposto a encontrar o erro para ele em troca de algumas centenas de dólares.

Para dar um contexto: recebo uma prova de P ≠ NP ou P = NP na minha caixa de entrada aproximadamente uma vez por mês. Muitos desses e-mails vão para uma longa lista de teóricos da complexidade (Cook, Karp, Fortnow, Sipser ...); eles geralmente incluem ruminações religiosas ou metafísicas, bem como sugestões sombrias sobre conspirações acadêmicas. (Em um caso, houve ameaças de morte gráficas contra mim, o que me levou a entrar em contato com a polícia.) Virtualmente, nenhum deles reconhece qualquer possibilidade de que a prova esteja errada ou que o autor possa ter entendido mal a pergunta. E quando, na faculdade, tentei me corresponder com os autores, descobri que todos acreditavam fervorosamente na máxima de Churchill "nunca, nunca, nunca, nunca desista".

Então, a solicitação do desenvolvedor de software realmente me impressionou! Foi a primeira vez que vi uma prova de PN acompanhada por esse nível de autoconsciência - tanto sobre a imposição feita no tempo das pessoas quanto (mais importante) sobre a probabilidade de erro. Por acaso, meu aluno de doutorado Michael Forbes enviou ao autor um relatório detalhado e bonito, explicando os problemas de sua abordagem; o autor agradeceu a Michael e (eu acho! :-)) pagou como prometido.

Então, sim: para amadores que desejam que alguém examine suas provas P vs. NP (ou trabalho semelhante), acho que pagar a um estudante de graduação algumas centenas de dólares é um ótimo caminho a percorrer. (Observe que os estudantes de pós-graduação são uma escolha muito melhor do que os professores: eles não apenas têm mais energia e entusiasmo por essas coisas, como também precisam mais do dinheiro.) Gostaria que mais amadores se aproveitassem dessa opção.

Por alguns meses, no final do meu último ano de faculdade e no início do meu primeiro ano de faculdade, ganhei US $ 60 / hora corrigindo as provas incorretas de um amador do Último Teorema de Fermat. Nesse caso, a pessoa era acadêmica em outro campo e, portanto, tinha um entendimento razoável do valor do tempo do especialista. Foi uma boa experiência, ganhei mil dólares em um momento em que não tinha outras boas fontes de renda, e ele aprendeu os erros que cometeu em vários rascunhos.

Penso que para as pessoas que estão fazendo um esforço genuíno e estão dispostas a pagar um bom dinheiro, não deve ser difícil encontrar graduandos qualificados ou jovens estudantes de pós-graduação que precisam de algum dinheiro.

Um problema que vejo com a sua sugestão é que a maioria das não provas de P vs NP nem sequer são falsas. Em outras palavras, eles geralmente sofrem de uma falha de definição ou especificação que os torna impossíveis de verificar como verdadeiro ou mostrar-se falso. Vou encaminhá-lo para minha caricatura (sem vergonha de autopromoção!) Da interação típica entre especialistas e o entusiasta amador de P vs NP : é difícil ver como a introdução de dinheiro nessa discussão o melhoraria.

ps a caricatura acima é baseada em observar naufrágios de trem na teoria: Timothy Chow pode ter mais a dizer sobre isso, já que muitas vezes tenta pacientemente envolver essas pessoas.

Lembro-me de ir a uma conferência de idiomas por volta de 1985, onde ocorreu a seguinte troca:

Orador: As folhas da árvore são exemplos de um problema NP-completo, mas são fáceis de resolver manualmente.

Eu: Se as instâncias são fáceis de resolver, talvez o problema não esteja completo.

Orador: Eu não entendo.

US $ 300 parece muito pouco para cobrar. Paga apenas uma hora ou duas vezes. Qualquer prova de que o short já foi descartada.

Definitivamente não. Ainda não precisamos de outra alternativa acadêmica. Certas pessoas já forneceram essas alternativas, proporcionando a pesquisadores amadores e profissionais e à sociedade falsas esperanças de um futuro de alta tecnologia (eu tenho um local específico em mente, mas prefiro não mencionar).

O sistema acadêmico foi forjado após séculos para o que é. Vejo tentativas de pular o sistema de revisão por pares simplesmente como "pular a linha". Se uma pesquisadora amadora não tem a capacidade de entender por que sua prova está errada, sozinha ou com alguns comentários a serem revisados, existe uma solução simples e é que ela deve estudar o assunto em questão. É por isso que instituições educacionais, como universidades, existem para certificar o conhecimento de uma determinada pessoa. Se essa pessoa for um gênio que capta o conhecimento do campo instantaneamente, tudo bem, conceda esse grau o mais rápido possível. Mas a grande maioria deve e deve ser treinada por eles e pela sociedade.

O que você pensaria se essa linha de negócios fosse retirada da matemática e colocada em medicina ou outro campo em que as consequências sejam mais imediatas? Quanto tempo até um empresário não confiável, de propósito, alterar os documentos amadores, para que sejam difíceis de revisar ou enganar o revisor? Enganar os clientes - pesquisadores amadores está fadado a acontecer, como acontece com todas as empresas que dependem muito de obter conhecimento.

Você pode ver que meu argumento é que existem problemas funcionais antes mesmo de investigar os detalhes técnicos. E como estou argumentando em engenharia, "programação" é um bom exemplo do que acontece quando amadores estão tentando fazer um trabalho sério com pouco ou nenhum treinamento. A última coisa que qualquer comunidade científica precisa é que a mídia glorifique o próximo "cientista da computação teórico autodidata que desafia os fundamentos de toda a comunidade científica de sua garagem", sem falar em uma ciência frágil como a nossa, que ainda tenta obter o reconhecimento. merece.