SILVIO MEIRA

será que P~=NP?

vinay deolalikar está propondo uma prova de que P~=NP. este é um dos mais radicais e importantes problemas da ciência da computação e, se resolvido, vai mudar o mundo. principalmente se deolalikar estiver errado e alguém conseguir provar justamente o contrário do que ele está propondo.

um monte de gente muito inteligente e dedicada está tentando provar que ou P=NP ou P~=NP há décadas. mas toda vez que alguém aparece com uma suposta prova, muito mais gente aparece com objeções a ela. não está sendo diferente com a “prova” de deolalikar.

a versão da prova publicada no 6 de agosto está neste link. são mais de cem páginas da matemática mais complexa que existe. o miolo da prova deveria ser o teorema abaixo. boa leitura. da cópia, aliás, porque deolalikar retirou o original de sua página e “está trabalhando em correções”, segundo fontes próximas. há quem acredite que a prova já era, foi só um sonho que durou tres dias.

imageimage

se você quiser saber mais sobre o problema em questão, este blog escreveu sobre o assunto em março de 2008, quando se tratava da existência de uma possível prova de que P=NP… o contrário do que deolalikar diz ter provado. o texto está replicado abaixo exatamente como apareceu e –logo depois-desapareceu, quando o TERRA trocou a plataforma de publicação, dando conta de que um professor da UFPE, em recife, talvez tivesse resolvido o problema.

a complexidade computacional de um problema é, em última análise, o tempo que se gasta, no pior caso, para resolvê-lo. problemas computacionais são resolvidos em computadores, usando algoritmos, que são seqüências de instruções bem definidas, que o computador [qualquer que seja] pode executar de forma precisa. por trás deste blog, há um conjunto de algoritmos, sendo executados por servidores no terra.com.br, para transformar os tecles e clicks do leitor em páginas visualizadas na tela.

algoritmos estão, na verdade, por trás de quase tudo o que acontece no mundo. o motor flex depende de algoritmos para analisar o resultado da compbustão e sintonizar o motor para a mistura de combustível que está no tanque. seu banco -on e off line- é uma montanha de algoritmos. assim como o sistema de saúde, o imposto de renda, a tv digital… o voar dos aviões, o sistema de controle de tráfego aéreo e por aí vai. não, os pássaros ainda não são informatizados e seu voar é livre. por enquanto.

pois bem. os problemas computacionais do tipo P são aqueles em que o tempo [ou o custo] para tratar uma instância qualquer do problema é, no máximo, de ordem polinomial. algo como o tamanho do problema elevado ao quadrado, por exemplo. ou o tamanho do problema multiplicado pelo logaritmo dele mesmo, que vem a ser a complexidade de ordenar um arquivo qualquer [ou de começar com uma lista desordenada de palavras e deixá-la, ao fim do algoritmo, ordenada].

há problemas cuja complexidade de solução depende de uma função não polinomial do tamanho da entrada, como seu fatorial [n! = 1* 2 * 3 * … * n]. gerar todas as permutações de um conjunto de N números gasta tempo N!, onde exclamação, aí atrás, é o símbolo para fatorial. que vem a ser uma função que cresce muito depressa. quer ver? se um problema tem complexidade fatorial e seu tamanho é 3 [três objetos como entrada…], o custo de resolvê-lo é 6 [pois 1 * 2 * 3 = 6]. tamanho 4 custa 24, 5 custa 120, 6 custa 720, 7 já vai pra 5040… e, se o problema for de tamanho 20, o custo é nada menos do que 2.432.902.008.176.640.000! quase dois e meio quintilhões. coisa de louco. isso faz com que problemas para os quais não se conhece uma solução polinomial sejam, via de regra, considerados computacionalmente intratáveis.

até aqui, dá pra entender o que são os problemas do tipo P: aqueles para os quais -mesmo em seu pior caso- a solução tem custo polinomial. e o NP, lá do título? NP é a classe problemas considerados computacionalmente "razoáveis", aqueles para os quais, dada uma possível solução, pode-se testá-la em tempo polinomial. ou seja, para os quais, se conseguirmos uma potencial solução de forma não determinística, temos um algoritmo lá da classe P que diz se a solução é verdeira ou não. talvez venha, daí, o nome da classe: N de "não determinístico" e P de polinomial. para mais detalhes sobre o assunto, de forma tão simples quanto é possível no caso, leia esta explicação do professor paulo feofiloff.

juntando as duas coisas, chegamos ao título do texto de hoje: será que há uma solução polinomial para todos os problemas computacionalmente razoáveis? será que, para cada e todo problema não determinístico polinomial [NP] eu consigo achar uma solução polinomial [em P]? ou seja, será que consigo provar que P=NP, que a classe dos problemas "razoáveis" tem complexidade polinomial, encerrando uma discussão iniciada em 1971 [por cook, veja aqui] e ganhando um prêmio de um milhão de dólares do clay institute? e isso contra a opinião da vasta maioria dos cientistas da área? em pesquisa recente, apenas 9 entre 100 cientistas que estão trabalhando no problema disseram acreditar que P=NP. e apenas 5 entre os 100 disseram que o problema seria resolvido -de uma forma ou de outra- antes de 2010.

se P=NP, haverá conseqüências muito interessantes do ponto de vista de [entre muitas outras áreas] logística, biologia, possivelmente criptografia e, talvez, toda a matemática. porque provar teoremas se tornaria muito mais fácil, segundo o próprio cook, o cientista que começou a discussão: …it [P=NP] would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time… em suma, parte da computação e matemática que está sendo feita e usada hoje pode mudar consideravelmente, com a provável inclusão, na lista, dos sistemas de segurança das transações financeiras. vai ser um auê federal. mundial, aliás.

sim. e daí? o leitor acorda na segunda e, primeira coisa que lê é este blog, com esta conversa mole e complicada sobre obscuridades matemáticas e computacionais quase ininteligíveis… o que é que o autor tá pensando? que isso aqui é aula de teoria da computação? não. este texto está aqui por duas razões. primeira: se P=NP, nossas vidas vão mesmo mudar. pode acreditar. segunda: um brasileiro [e trabalhando no brasil], sóstenes lins, professor titular do departamento de matemática da ufpe, anunciou em seminário recente, em recife, estar finalizando os detalhes de uma prova definitiva de que, sim, P=NP. agora é esperar pra ver os detalhes. boa sorte, sóstenes.

* . * . *

PS1: paulo feofiloff chamou minha atenção para a "lista de woeginger", que tenta acompanhar todas [e até agora malfadadas] tentativas de provar que P é ou não igual a NP. para quem estiver interessado nas definições, debates e tentativas de prova que cercam a controvérsia, é sem dúvida uma boa fonte.

Outros posts

E AÍ… IA [II]

Trabalho, Emprego e IA   Há uma transformação profunda do trabalho e da produção, como parte da transformação figital dos mercados, da economia e da

EFEITOS DE REDE E ECOSSISTEMAS FIGITAIS [XV]

Uma série, aqui no blog [o primeiro texto está em… bit.ly/3zkj5EE, o segundo em bit.ly/3sWWI4E, o terceiro em bit.ly/3ycYbX6, o quarto em… bit.ly/3ycyDtd, o quinto

E AÍ, IA… [I]

IA fará com que todos sejam iguais em sua capacidade de serem desiguais. É o maior paradoxo desde que Yogi Berra disse… ‘Ninguém mais vai

Efeitos de Rede e Ecossistemas Figitais [XII]

Uma série, aqui no blog [o primeiro texto está em… bit.ly/3zkj5EE, o segundo em bit.ly/3sWWI4E, o terceiro em bit.ly/3ycYbX6, o quarto em… bit.ly/3ycyDtd, o quinto

Efeitos de Rede e Ecossistemas Figitais [xi]

Uma série, aqui no blog [o primeiro texto está em… bit.ly/3zkj5EE, o segundo em bit.ly/3sWWI4E, o terceiro em bit.ly/3ycYbX6, o quarto em… bit.ly/3ycyDtd, o quinto

Efeitos de Rede e Ecossistemas Figitais [x]

Uma série, aqui no blog [o primeiro texto está em… bit.ly/3zkj5EE, o segundo em bit.ly/3sWWI4E, o terceiro em bit.ly/3ycYbX6, o quarto em… bit.ly/3ycyDtd, o quinto

Efeitos de Rede e Ecossistemas Figitais [ix]

Uma série, aqui no blog [o primeiro texto está em… bit.ly/3zkj5EE, o segundo em bit.ly/3sWWI4E, o terceiro em bit.ly/3ycYbX6, o quarto em… bit.ly/3ycyDtd, o quinto

Efeitos de Rede e Ecossistemas Figitais [vi]

Uma série, aqui no blog [o primeiro texto está em… bit.ly/3zkj5EE, o segundo em bit.ly/3sWWI4E, o terceiro em bit.ly/3ycYbX6, o quarto em… bit.ly/3ycyDtd, o quinto

Efeitos de Rede e Ecossistemas Figitais [v]

Uma série, aqui no blog [o primeiro texto está em… bit.ly/3zkj5EE, o segundo em bit.ly/3sWWI4E, o terceiro em bit.ly/3ycYbX6, o quarto em… bit.ly/3ycyDtd, o quinto

Efeitos de Rede e Ecossistemas Figitais [iv]

Uma série, aqui no blog [o primeiro texto está em… bit.ly/3zkj5EE, o segundo em bit.ly/3sWWI4E, o terceiro em bit.ly/3ycYbX6, o quarto em… bit.ly/3ycyDtd, o quinto

chatGPT: cria ou destrói trabalho?

O potencial de relevância e impacto inovador de transformadores [veja A Grande Transformação dos Transformadores, em bit.ly/3iou4aO e ChatGPT is everywhere. Here’s where it came

A Grande Transformação dos Transformadores

Um transformador, na lembrança popular, era [ainda é] a série de filmes [Transformers, bit.ly/3Qp97cu] onde objetos inanimados, inconscientes e -só por acaso- alienígenas, que existiam

Começou o Governo. Cadê a Estratégia?

Estamos em 02/01/2023. Ontem foram as posses e os discursos. Hoje começam a trabalhar um novo Presidente da República, dezenas de ministros e ainda serão

23 anotações sobre 2023 [xxiii]

Este é o 23° de uma série de textos sobre o que pode acontecer, ou se tornar digno de nota, nos próximos meses e poucos

23 anotações sobre 2023 [xxii]

Este é o 22° de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [xxi]

Este é o 21° de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [xx]

Este é o 20° de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [xix]

Este é o 19° de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [xviii]

Este é o 18° de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [xvii]

Este é o 17° de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [xvi]

Este é o 16° de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [xv]

Este é o 15° de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [xiv]

Este é o décimo quarto de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se

23 anotações sobre 2023 [xiii]

Este é o décimo terceiro de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se

23 anotações sobre 2023 [xii]

Este é o décimo segundo de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se

23 anotações sobre 2023 [xi]

Este é o décimo primeiro de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se

23 anotações sobre 2023 [x]

Este é o décimo de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [ix]

Este é o nono de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [viii]

Este é o oitavo de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [vii]

Este é o sétimo de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [vi]

Este é o sexto de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [v]

Este é o quinto de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [iv]

Este é o quarto de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [iii]

Este é o terceiro de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [ii]

Este é o segundo de uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar

23 anotações sobre 2023 [i]

Esta é uma série de textos curtos, de uns poucos parágrafos e alguns links, sobre o que pode acontecer, ou se tornar digno de nota,

Efeitos de Rede e Ecossistemas Figitais [ii]

Uma série, aqui no blog [o primeiro texto está em… bit.ly/3zkj5EE, o segundo em bit.ly/3sWWI4E, o terceiro em bit.ly/3ycYbX6, o quarto em… bit.ly/3ycyDtd, o quinto

Efeitos de Rede e Ecossistemas Figitais [i]

Uma série, aqui no blog [o primeiro texto está em… bit.ly/3zkj5EE, o segundo em bit.ly/3sWWI4E, o terceiro em bit.ly/3ycYbX6, o quarto em… bit.ly/3ycyDtd, o quinto

O Metaverso, Discado [4]

Este é o quarto post de uma série dedicada ao metaverso. É muito melhor começar lendo o primeiro [aqui: bit.ly/3yTWa3g], que tem um link pro

O Metaverso, Discado [3]

Este é o terceiro post de uma série dedicada ao metaverso. É muito melhor começar lendo o primeiro [aqui: bit.ly/3yTWa3g], que tem um link pro

O Metaverso, Discado [2]

Este é o segundo post de uma série dedicada ao metaverso. É muito melhor ler o primeiro [aqui: bit.ly/3yTWa3g] antes de começar a ler este aqui. Se puder, vá lá, e volte aqui.

O Metaverso, Discado [1]

O metaverso vai começar “discado”. E isso é bom. Porque significa que vai ser criado e acontecer paulatinamente. Não vai rolar um big bang vindo

chega de reuniões

um ESTUDO de 20 empresas dos setores automotivo, metalúrgico, elétrico, químico e embalagens mostra que comportamentos disfuncionais em REUNIÕES [como fugir do tema, reclamar, criticar…

Definindo “o” Metaverso

Imagine o FUTEBOL no METAVERSO: dois times, A e B, jogam nos SEUS estádios, com SUAS bolas e SUAS torcidas. As BOLAS, cada uma num

Rupturas, atuais e futuras,
no Ensino Superior

Comparando as faculdades com outras organizações na sociedade,percebe-se que sua peculiaridade mais notável não é seu produto,mas a extensão em que são operadas por amadores.

O que é Estratégia?

A primeira edição do Tractatus Logico-Philosophicus [TLP] foi publicada há exatos 100 anos, no Annalen der Naturphilosophie, Leipzig, em 1921. Foi o único livro de

O Brasil Tem Futuro?

Uma das fases mais perigosas e certamente mais danosas para analisar e|ou entender o nosso país é a de que “O Brasil é o país

Os Velhos Envelopes, Digitais

Acho que o último envelope que eu recebi e não era um boleto data da década de 1990, salvo uma ou outra exceção, de alguém

Houston, nós temos um problema…

Este texto é uma transcrição editada de uma intervenção no debate “De 1822 a 2022 passando por 1922 e imaginando 2122: o salto [?] da

Pessoas, Games, Gamers, Cavalos…

Cartas de Pokémon voltaram à moda na pandemia e os preços foram para a estratosfera. Uma Charizard holográfica, da primeira edição, vale dezenas de milhares

As Redes e os Currais Algorítmicos

Estudos ainda limitados[1] sobre política e sociedade mostram que a cisão entre centro [ou equilíbrio] e anarquia [ou caos] é tão relevante quanto a divisão

O Trabalho, em Transição

Trabalho e emprego globais estão sob grande impacto da pandemia e da transformação digital da economia, em que a primeira é o contexto indesejado que

O ano do Carnaval que não houve

Dois mil e vinte e um será, para sempre, o ano do Carnaval que não houve. Quem sentirá na alma são os brincantes para quem

Rede, Agentes Intermediários e Democracia

Imagine um provedor de infraestrutura e serviços de informação tomando a decisão de não trabalhar para “um cliente incapaz de identificar e remover conteúdo que

21 anotações sobre 2021

1 pode até aparecer, no seu calendário, que o ano que vem é 2021. mas não: é 2025. a aceleração causada por covid19, segundo múltiplas

A Humanidade, em Rede

Redes. Pessoas, do mundo inteiro, colaborando. Dados, de milhares de laboratórios, hospitais, centros de pesquisa e sistemas de saúde, online, abertos, analisados por sistemas escritos

tecnologia e[m] crises

tecnologia, no discurso e entendimento contemporâneo, é o mesmo que tecnologias da informação e comunicação, TICs. não deveria ser, até porque uma ponte de concreto

o que aconteceu
no TSE ontem?

PELA PRIMEIRA VEZ em muitos anos, o BRASIL teve a impressão de que alguma coisa poderia estar errada no seu processo eleitoral, e isso aconteceu

CRIAR um TEMPO
para o FUTURO

em tempos de troca de era, há uma clara percepção de que o tempo se torna mais escasso. porque além de tudo o que fazíamos

Duas Tendências Irreversíveis, Agora

O futuro não acontece de repente, todo de uma vez. O futuro é criado, paulatinamente, por sinais vindos de lá mesmo, do futuro, por caminhos

futuro: negócios e
pessoas, figitais

em tempos de grandes crises, o futuro, às vezes mais do que o presente, é o centro das preocupações das pessoas, famílias, grupos, empresas e

bom senso & saber

uma pergunta que já deve ter passado pela cabeça de muita gente é… o que é o bom senso, e como é que a gente

uma TESE são “só” 5 coisas…

…e uma dissertação e um trabalho de conclusão de curso, também. este post nasceu de um thread no meu twitter, sumarizando perguntas que, durante a

os novos NORMAIS serão FIGITAIS

há muitas empresas achando que… “agora que COVID19 está passando, bora esquecer essa coisa de DIGITAL e trazer os clientes de volta pras lojas”… enquanto

Novas Formas de Pensar em Tempos Incertos

O HOMO SAPIENS anatomicamente moderno tem ceca de 200.000 anos. Há provas de que tínhamos amplo controle do fogo -talvez “a” tecnologia fundadora da humanidade-

Efeitos não biológicos de COVID19

A PARTIR do que já sabemos, quais os impactos e efeitos de médio e longo prazo da pandemia?… O que dizem as pesquisas, não sobre

APRENDER EM VELOCIDADE DE CRISE

TODOS OS NEGÓCIOS estiveram sob gigantesca pressão para fazer DUAS COISAS nas últimas semanas, quando cinco décadas de um processo de transformação digital que vinha,

UM ANTIVÍRUS para a HUMANIDADE

SARS-COV-2 é só um dos milhares de coronavírus que a ciência estima existir, ínfima parte dos 1,7 milhões de vírus desconhecidos que os modelos matemáticos

Mundo Injusto, Algoritmos Justos?

Se um sistema afeta a vida das pessoas, exige-se que seu comportamento seja justo. Pelo menos no que costumamos chamar de civilização. Ser justo é

Das nuvens, também chovem dados

Há uns meses, falamos de Três Leis da Era Digital, inspiradas nos princípios de Asimov para a Robótica. As Leis eram… 1ª: Deve-se proteger os

As Três Leis da Era Digital

Há setenta e oito anos, Isaac Asimov publicava a primeira versão do que todos conhecem como as Três Leis da Robótica[1]. A Primeira diz que

o apocalipse digital…

…segundo silvio meira, capítulo 55, versículo 2019, parágrafos 1 a 8. escrito em plena sexta-feira 13, num dos grupos de inovação [corporativa] mais animados e

por uma educação
“sem” distância

Uma versão editada do texto abaixo foi publicada no ESTADÃO em 28/08/2019, quando ninguém tinha a menor ideia de que toda a educação do país

uma classe para o brasil

este texto tem origem numa discussão [em grupos de zap, que depois se tornaram mesas de bar…] sobre o protagonismo do brasil em um particular cenário

Silvio Meira é cientista-chefe da TDS.company, professor extraordinário da CESAR.school e presidente do conselho do PortoDigital.org

contato@tds.company

Rua da Guia, 217, Porto Digital Recife.

tds.company
somos um negócio de levar negócios para o futuro, nosso objetivo é apoiar a transformação de negócios nascentes e legados nas jornadas de transição entre o presente analógico e o futuro digital.

strateegia
é uma plataforma colaborativa de estratégia digital para adaptação, evolução e transformação de negócios analógicos em plataformas e ecossistemas digitais, desenvolvido ao longo de mais de uma década de experiência no mercado e muitas na academia.