Papéis engraçados relacionados ao TCS etc?

80

Qual é o trabalho publicado mais engraçado sobre TCS que você conhece?

Por favor, inclua apenas aqueles que pretendem ser engraçados. Os trabalhos explicitamente criados para serem inteligentemente bem-humorados (em vez de, digamos, uma coleção publicada de piadas curtas sobre a teoria da complexidade) são os preferidos. Trabalhos com títulos engraçados (na verdade engraçados, não apenas engraçados) também são aceitos.

Por favor, apenas um trabalho por resposta para que os "melhores" possam chegar ao topo.

Joshua Grochow
fonte
3
e os papéis com títulos engraçados? ou deveria ser uma pergunta diferente?
Suresh Venkat
4
Eu acho que títulos engraçados estão bem :).
Joshua Grochow
1
Por que apenas complexidade (e não outros tópicos do TCS)? E os livros? (Gostaria de postar Matemática Concreta :))
Kaveh
3
por alguma razão, mathoverflow.net/questions/44326/most-memorable-titles é um encadeamento relacionado.
RJK
2
@Suresh: Eu acredito que você quer dizer xxx.lanl.gov/abs/1003.6064v1
Radu GRIGore

Respostas:

52

O Problema do Papel Higiênico (Donald Knuth, American Mathematical Monthly, 1984). Desde a introdução:

Os dispensadores de papel higiênico de um determinado prédio são projetados para acomodar dois rolos de lenços de papel e uma pessoa pode usá-los. Existem dois tipos de pessoas que usam os banheiros do prédio: grandes e pequenos compradores. Um grande comprador sempre tira um pedaço de papel higiênico do rolo que é maior no momento; um pouco de escolha sempre faz o oposto. No entanto, quando os dois rolos são do mesmo tamanho ou quando apenas um rolo é vazio, todo mundo escolhe o rolo não vazio mais próximo. Quando os dois rolos estão vazios, todo mundo tem um problema.
cristã
fonte
24
Ah não. Knuth me venceu. Eu havia considerado uma questão relacionada, reconhecidamente mais simples, e me convenci de que todo mundo deveria escolher pouco para minimizar o risco cooperativamente (e eu sou um desde então). Mas nunca tive tempo de escrever o resultado. Pelo menos, fico feliz em conhecer o trabalho anterior antes de escrevê-lo e submetê-lo à Conferência Internacional sobre Banheiros Teóricos.
Tsuyoshi Ito
5
Houve aparência semi-rigorosos no problema de seleção mictório de um POV algoritmos: blog.xkcd.com/2009/09/02/urinal-protocol-vulnerability
Andy Drucker
38

Kyle Burke e David Charlton. Limites inferiores por tempo polinomial provavelmente isístico. Universidade de Boston, 2005. (Obrigado ao @arnab e ao Web Archive pelo link.)

Tenho certeza de que este foi um artigo do April Fool, mas de qualquer forma é absolutamente hilário. O resumo:

Preenchemos uma lacuna na teoria da complexidade existente, introduzindo a classe de cálculos de tempo polinomial provavelmente realista, isto é, cálculos que, você sabe, provavelmente terminam no tempo polinomial, tanto quanto sabemos. Aplicamos essa classe para mostrar que algoritmos para problemas completos de NP provavelmente não são executados em tempo polinomial.

Joshua Grochow
fonte
6
Entendi! Não consigo encontrá-lo vinculado a partir de nenhuma página da web existente, mas você pode recuperá-lo aqui: web.archive.org/web/20080211140314/http://cs-people.bu.edu/…
arnab
3
Eu estava em uma classe com David Charlton em 2002, quando ele era um estudante, então eu tenho quase certeza que deve ser 2005 não 1995 ;-)
Mugizi Rwebangira
1
David escreveu isso como uma resposta hilária a um comentário que fiz na pós-graduação. Não me lembro do meu comentário exato, mas o jornal é hilário! : -DI não pode receber nenhum crédito real pela hilaridade.
Kyle
30

Andrew W. Appel, " O POPL é Matemática ou Ciência? "

Este trabalho estuda as conferências de CS e tenta classificá-las como teóricas ou aplicadas com base em se os autores ordenam seus nomes em ordem alfabética (teórica) ou por contribuição (aplicada).

Robin Kothari
fonte
4
Adoro o final "O objetivo da pesquisa apresentada neste relatório foi dar risadas no POPL '92; fico feliz em dizer que, a esse respeito, a pesquisa foi inteiramente bem-sucedida".
Dave Clarke
Eu adoraria ver isso continuou até os dias atuais
Thomas Ahle
24

Vários documentos de Jean-Yves Girard .

Seu artigo Linear Logic tem a seguinte nota de rodapé do editor da revista Theoretical Computer Science:

Devido à sua extensão e novidade, este artigo não foi submetido ao processo normal de arbitragem. O editor está preparado para compartilhar com o autor qualquer crítica que eventualmente seja expressa a respeito deste trabalho.

Outro é o Locus Solum, das regras da lógica à lógica das regras . O artigo de 192 páginas possui um apêndice com quase 100 páginas chamado " Um desperdício puro de papel ", o apêndice mais engraçado que eu já vi.

Kaveh
fonte
12
O mais extraordinariamente estranho é que "um puro desperdício de papel" é realmente muito bom. Você não pode confiar ingenuamente em qualquer coisa que ele escreva, mas, no entanto, há um ponto sério sobre a lógica oculta em quase todas as piadas / insultos / aparte.
Neel Krishnaswami
3
Leitores de língua francesa pode desfrutar de seu artigo sobre relógios de mostarda
Gallais
1
Infelizmente, o terceiro link está quebrado.
Max
3
@ galais: Na verdade, a versão original do artigo "Mustard watches" está em inglês e pode ser encontrada aqui .
Damiano Mazza
1
Esta é a "correção" para o link na resposta principal: iml.univ-mrs.fr/~girard/0.pdf
apnorton
22

O artigo de Yonatan Bilu, Dana Porrat e Yoav Yaffe " Sobre o número de preservativos em uma orgia barata de sexo seguro ". Este artigo não foi publicado e, portanto, não corresponde a um dos requisitos (trabalho a ser publicado). Mas acho que pode ser incluído aqui como uma exceção.

Oleksandr Bondarenko
fonte
Eu acho que isso pode estar relacionado: mathworld.wolfram.com/GloveProblem.html
RJK
4
@Oleksander: A exigência de "publicado" não era para ser rigoroso, mas a intenção de separar coisas como artigos e livros de, digamos, tiras de banda desenhada (caso contrário, esta discussão poderia ser preenchidos com referências xkcd.)
Joshua Grochow
Na mesma linha: Ménage à Trois, Degenerados e Triângulos amorosos de Grønlund e Pettie. É realmente um artigo sério, de complexidade refinada, e a piada no título é forçada.
precisa saber é o seguinte
20

De fato, existe todo um diário que se destina a ser engraçado. O jornal de craptologia . Os tópicos geralmente estão relacionados à criptografia. Existem também algumas sessões de vídeos (!)

Um exemplo é o artigo do Volume 4 de Criptografia no Universo de um Mochileiro (seção 5):

Atrações próximas

Se você gostou da nossa apresentação de recursos, ficará feliz em saber sobre as próximas atrações do mesmo autor:

- A criptoanálise de sistemas de protocolo interativo humano. Uma controversa análise criptográfica do artigo de Shakira [4], que prova que os HIPS, de fato, mentem.

- Conhecimento anti-zero. Um sistema de protocolo que revela tudo o que um provador sabe, exceto o que o verificador deseja ouvir. Protocolos ad-hoc anti-conhecimento zero foram desenvolvidos pela maioria dos serviços de atendimento ao cliente.

- Distribuição de chaves quânticas baseada em fenômenos sociais. Este artigo demonstra como distribuir chaves usando técnicas quânticas, mas sem o uso de objetos quânticos. Em vez de usar objetos quânticos, o protocolo usa a incerteza que qualquer homem tem sobre se sua primeira noite com uma mulher conta como uma data ou não para transmitir as chaves.

. M. Alaggan
fonte
17

Matemática Concreta: Uma Fundação para Ciência da Computação , de Ronald Graham, Donald Knuth e Oren Patashnik.

Um livro incrível com muitas notas laterais engraçadas. :) (Veja também a página GKP do DEK .)

Kaveh
fonte
4
As anotações são realmente engraçadas, mas o livro é "simplesmente agradável" - garantido, nem todos podem escrever um livro agradável ;-) De qualquer forma, não sei se ele se qualifica como um trabalho engraçado, mas você recebe meu voto porque Eu gosto muito do livro.
Anthony Labarre
1
Este é o meu livro favorito. Estou surpreso que mais autores não tenham seguido seu formato.
Chad Brewbaker
17

Eu recomendaria os processamentos da FUN: a Conferência Internacional sobre Diversão com Algoritmos.

Devo dizer que "A dureza do jogo Lemmings, ou Oh não, mais provas de completude de NP" de Graham Cormode é uma das minhas favoritas.

Swann Perarnau
fonte
2
Acabei de encontrar os procedimentos da FUN de 2007 nos livros de Powell na semana passada - eu sinceramente apóio essa recomendação! Alguns ótimos resultados em classificação pessimal e algoritmos de paginação piores possíveis.
Steven Stadnicki
16

Uma proposta terminológica de Don Knuth . SIGACT News, 6 (1), 1974. Mencionado no The Complexity Blog. Aparentemente, foi aqui que obtivemos os termos "NP-complete" e "NP-hard".

Uma das minhas favoritas desta peça é a sugestão de Albert Meyer de que o que chamamos agora de problemas de NP-hard seja chamado de Hard-as-Satisfiability, ou hard-as-S, para abreviar.

Joshua Grochow
fonte
14

Confira a figura que acompanha o artigo SODA de 1 página de Adam Kalai, "Gerando números fatorados aleatórios facilmente": link

Aaron Roth
fonte
12

A. Broder, J. Stolfi " Algoritmos pessimais e análise de simplicidade ", ACM SIGACT News 16 (3), outono de 1984.

O artigo introduz "um ramo inteiramente novo da Ciência da Computação, o design e a análise de algoritmos relutantes. Intuitivamente, um algoritmo relutante para um problema P é aquele que perde tempo de uma maneira que é suficiente para enganar um observador ingênuo".

Hermann Gruber
fonte
9

O parlamento de Lamport em tempo parcial fez um avanço na computação distribuída, mas o artigo ficou tão (intencionalmente) ofuscado que as pessoas não conseguiam entendê-lo - até onde eu sei, ele levou cerca de 10 anos para publicá-lo (editores anteriores) em sua forma ofuscada. Eventualmente, Lamport seguiu Paxos Made Simple , que tinha o seguinte resumo: " O algoritmo Paxos, quando apresentado em inglês simples, é muito simples ".

Lev Reyzin
fonte
9

A Associação de Heresia Computacional da CMU tem vários deles, que são apresentados na conferência anual do SIGBOVIK (realizada em 04/01/2011). Meu favorito pessoal é:

Uma abordagem baseada em roubo para aquisição de objetos em 3D.

user2333
fonte
8

No mesmo espírito do post de Murilo da Silva, não resisto a publicar este trecho dos "Ciclos N de factoring e mapas de contagem de gêneros" de Goupil e Schaefer :

Após essa prova, incentivamos o leitor a fazer uma pausa e desfrutar de uma atividade mais leve, como observação de pássaros ou jardinagem, antes de prosseguir com a leitura.

Anthony Labarre
fonte
7

"Refinamento no formalismo baseado no Estado", de Lamport.

Um amigo nosso, que era um matemático brilhante, foi hospitalizado por causa do abuso a longo prazo de drogas alucinógenas. Decidimos dar a ele um relógio digital para seu quarto. No entanto, seu médico sugere que a hora e os minutos exibidos juntos possam ser muito confusos. Colocamos fita no visor dos minutos, transformando nosso presente em um relógio digital de hora.

Marcus Ritt
fonte
7

Acabei de descobrir "Uma carta do autor frustrado de um jornal" . Boa leitura ;-)

Anthony Labarre
fonte
1
Eu ouvi muito sobre esses processos para rejeitar a carta imediatamente como sátira. Eu me pergunto se é, no entanto. Caso contrário, estou com medo.
Raphael
6

Me deparei com o "Complexity Theory Newsflash" em algum momento e achei muito engraçado.

Ryan Williams
fonte
Agradável! Trabalhar com eles também serve como uma boa atualização em alguns dos resultados clássicos de complexidade.
András Salamon
6

Títulos engraçados recentes:

  • A. Kehagias, P. Pralat, Algumas observações sobre policiais e ladrões bêbados , Ciência da Computação Teórica 463 (2012) 133-147, DOI

  • A. Kehagias, D. Mitsche, P. Pralatb, Policiais e ladrões invisíveis: O custo da embriaguez , Teoria da Computação (2013), na Imprensa

  • Natasha Komarov, Peter Winkle, Capturando o ladrão bêbado em um gráfico , maio de 2013, arXiv: 1305.4559

user13136
fonte
5

O discurso de Alice e Bob depois do jantar de John Gordon.

Boa conversa descontraída sobre a teoria da codificação.

Jagadish
fonte
É divertido quanto do que ele afirma que sua calculadora de bolso poderia fazer é agora possível em um smartphone moderno. Não exibe holográficas em 3D ainda, e você pode ser duramente pressionado para encontrar um compilador de ADA para Android, mas fora isso ...
AlexC
4

Agora não consigo pensar em um artigo engraçado, mas me lembro de um artigo "normal" que continha uma linha engraçada. Foi de fato a primeira frase da Seção 1. Os autores começaram o artigo com:

"Ao contrário da nossa prática usual, nos sentimos obrigados a começar este trabalho com algumas definições". Então deixe G ... "

O título do artigo é " $beta$-perfect graphs", de Markossian, Gasparian e Reed, em 1996. Ele chamou minha atenção porque é de fato um artigo-chave sobre a teoria perfeita dos grafos, onde é definida a classe de gráficos beta-perfeitos, uma classe que é, de certa forma, análoga aos gráficos perfeitos (os gráficos beta-perfeitos são uma subclasse dos gráficos sem buracos no EVEN, enquanto os gráficos perfeitos são uma subclasse dos gráficos sem buracos no ODD.

Murilo da Silva
fonte
Também conhecido como "Como essa é uma palestra sobre teoria, eu começaria definindo o problema sobre o qual estou falando ..."
Sariel Har-Peled
3

Lambda the Ultimate chamou a minha atenção o whitepaper sobre Fósforo, o Popular Lisp , que se "Popular Lisp" não lhe der uma dica, é satírico ^ _-

paul.meier
fonte