Em janeiro de 2020, Papadimitriou estava pensando no princÃpio do Pigeohole há 30 anos. Então ele ficou surpreso quando uma conversa lúdica com um colaborador frequente os levou a uma reviravolta simples com o princÃpio que eles nunca consideraram: e se houver menos pombos do que buracos? Nesse caso, qualquer arranjo de pombos deve deixar alguns orifÃcios vazios. Mais uma vez, parece óbvio. Mas invertendo o princÃpio do pombo tem alguma conseqüência matemática interessante?
Pode parecer que esse princÃpio “PiGeonhole vazio” é apenas o original por outro nome. Mas não é, e seu caráter sutilmente diferente o tornou uma ferramenta nova e frutÃfera para classificar os problemas computacionais.
Para entender o princÃpio vazio de pigeonehole, vamos voltar ao exemplo do cartão, transposta de um estádio de futebol para uma sala de concertos com 3.000 assentos-um número menor do que o total de pinos de quatro dÃgitos possÃveis. O princÃpio vazio de pigeonehole determina que alguns pinos possÃveis não estão representados. Se você deseja encontrar um desses pinos ausentes, porém, não parece haver nenhuma maneira melhor do que simplesmente perguntar a cada pessoa o seu alfinete. Até agora, o princÃpio vazio de pigeonhole é exatamente como seu colega mais famoso.
A diferença está na dificuldade de verificar soluções. Imagine que alguém diz que encontrou duas pessoas especÃficas no estádio de futebol que têm o mesmo alfinete. Nesse caso, correspondendo ao cenário original do Pigeonhole, há uma maneira simples de verificar essa afirmação: basta verificar com as duas pessoas em questão. Mas no caso da sala de concertos, imagine que alguém afirma que nenhuma pessoa tem um alfinete de 5926. Aqui, é impossÃvel verificar sem perguntar a todos na platéia qual é o seu alfinete. Isso torna o princÃpio vazio de pigeonehole muito mais irritante para os teóricos da complexidade.
Dois meses depois que Papadimitriou começou a pensar sobre o princÃpio vazio de PiGeonhole, ele o criou em uma conversa com um estudante de graduação em potencial. Ele se lembra de isso vividamente, porque acabou sendo sua última conversa pessoal com qualquer pessoa antes dos bloqueios Covid-19. Preir em casa nos meses seguintes, ele lutou com as implicações do problema para a teoria da complexidade. Eventualmente ele e seus colegas publicaram um papel Sobre problemas de pesquisa que têm soluções por causa do princÃpio de PiGeonhole vazio. Eles estavam especialmente interessados ​​em problemas em que os pombos são abundantes – isto é, onde superam em muito os pombos. De acordo com uma tradição de Acrônimos pesados Na teoria da complexidade, eles apelidaram dessa classe de problemas APEPP, para “o abundante princÃpio polinomial vazio de Pigeonhole”.
Um dos problemas nesta classe foi inspirado por um famoso Prova de 70 anos pelo cientista da computação pioneiro Claude Shannon. Shannon provou que a maioria dos problemas computacionais deve ser inerentemente difÃcil de resolver, usando um argumento que se baseava no princÃpio de piGeonhole vazio (embora ele não tenha chamado assim). No entanto, durante décadas, os cientistas da computação tentaram e não provaram que problemas especÃficos são realmente difÃceis. Como os alfinetes de cartas de banco, os problemas difÃceis devem estar lá fora, mesmo que não possamos identificá-los.
Historicamente, os pesquisadores não pensaram no processo de procurar problemas difÃceis como um problema de pesquisa que poderia ser analisado matematicamente. A abordagem de Papadimitriou, que agrupou esse processo com outros problemas de pesquisa relacionados ao princÃpio de pigeohole vazio, tinha um sabor auto-referencial caracterÃstico de muito trabalho recente Na teoria da complexidade – ofereceu uma nova maneira de raciocinar sobre a dificuldade de provar dificuldades computacionais.
