Um breve resumo dessa sopa de letrinhas da complexidade computacional.
P – Problemas que podem ser RESOLVIDOS em tempo polinomial.
NP – Problemas que podem ser VERIFICADOS em tempo polinomial.
NP complete – Os problemas mais difíceis da classe NP.
PSPACE – Problemas que necessitam de uma quantidade polinomial de memória.
BQP – Problemas de podem ser resolvidos eficientemente num computador quântico.
Uma explicação mais elaborada.
P – São os problemas “fáceis” de serem resolvidos.
NP – São os problemas “fáceis” de serem verificados. Ou seja, dada uma resposta, é fácil verificar se ela atende ou não o problema. Porém, não é necessariamente fácil chegar à solução.
Portanto, podem existir problemas que são fáceis de verificar, porém difíceis de resolver.
Exemplo simples. Rearrumar a palavra a seguir:
lrsdhreeaaamb
É bem mais difícil encontrar a solução do que verificar que “desembaralhar” é a resposta.
Os problemas mais difíceis de todos os NP são chamados NP-Completos. Diversos problemas da vida real, como o da Satisfiabilidade, são NP-Completos.
Existe também o NP-Hard, que são problemas pelo menos tão difíceis quanto os NP-completo. Problemas de otimização são assim. NP-Completo é achar uma solução, o NP-Hard, achar a melhor solução. O famoso problema do Caixeiro-Viajante é um exemplo de problema de otimização.
Um grande problema não resolvido do mundo é se P = NP. Até hoje, não foi possível provar que são iguais ou não diferentes. É, inclusive, um dos desafios do milênio do Instituto Clay, valendo 1 milhão de dólares!
O BQP são problemas resolvíveis por um computador quântico. Suspeita-se que seja possível resolver problemas mais difíceis que a classe P, porém sem resolver o NP-completo.
Portanto, a figura que representa os graus de complexidade é apenas uma ideia. Se P for igual a NP, nem precisaríamos de computador quântico! Bastaria usar esse algoritmo, que resolve problemas difíceis de forma fácil.
O problema P vs NP é complicado de provar, não à toa, até hoje não foi resolvido.
Porém, até hoje os problemas difíceis continuam difíceis, o que é um forte indício de que P é diferente de NP, e que problemas difíceis continuarão difíceis – e que computadores quânticos serão muito úteis.
“Preparados para o risco”, do autor alemão Gerd Gigerenzer, nos ensina a questionar os números, e com isso, tomarmos boas decisões.
Quatro highlights abaixo.
1 – Pergunte pelo significado.
“Amanhã, tem 30% de chance de chuva”. O que isso significa?
O 30% pode ter várias interpretações. 30% do dia vai chover. Há chance 30% de alguma chuva. No estado todo, vai chover em 30% da área…
Sem uma clara definição, não dá para saber o significado.
Exemplo: As manchetes dos últimos dias dizem que “a taxa de isolamento está em 49% e o ideal é 70%, segundo o governo”. O número é calculado a partir de rastreamento de celulares.
Mas, o que significa essa taxa de isolamento?
Se eu ficar em casa o dia inteiro, mas der uma voltinha, vai contar que estou furando o isolamento ou não?
2 – Pergunte pelos números relativos e absolutos
O autor cita uma manchete espalhafatosa: “Segunda geração de pílula anticoncepcional aumenta casos de trombose em 100%”.
A informação acima levou uma geração inteira de mulheres a evitar a pílula (e assim, aumentar a chance de gravidez).
Investigando o caso a fundo, num universo de 7.000 mulheres, os casos de trombose tinham aumentado de 1 para 2! Realmente, era um aumento de 100% nos casos, porém, são tão poucos casos que não há significado estatístico na conclusão citada. Ou seja, não havia motivo algum para o pânico gerado.
Como diz uma piada, “Estatística é a arte de torturar os números até que eles confessem.”
3 – Regras de bolso podem ser úteis.
Num mundo cada vez mais complexo, as pessoas têm a impressão de que necessitamos de soluções igualmente sofisticadas. Porém, não há sistema que consiga levar em conta tantas incertezas de um número enorme de variáveis possíveis.
Nesses casos, heurísticas simples e robustas são mais eficazes. Exemplo. O avião que pousou no rio Hudson, em 2009, usou a regra do polegar. Fique de olho na torre, se ela sumir do para-brisa, não há como chegar à pista. Decidiram pousar no rio Hudson.
Menos é mais. Faça o simples. Utilize regras simples em ambientes complexos.
Da mesma forma, não compre produtos financeiros que não entenda.
4 – Falsos positivos e falsos negativos podem ocorrer.
Gigerenzer ensinou mais de 1000 médicos em sua carreira, e estima que 80% não entendem o que um exame médico positivo significa, por não entenderem o que é um falso positivo e um falso negativo.
Uma recomendação é refazer um exame diversas vezes, não acreditar puramente no primeiro resultado.
Uma consequência é a chamada “medicina defensiva”. Por receio de que os pacientes o processem, os médicos acabam tomando medidas superprotetoras, o que leva a procedimentos médicos desnecessários.
Uma heurística simples: Não perguntar ao médico o que fazer. Perguntar ao médico o que ele faria, se estivesse no seu lugar.
Conclusão: o livro apresenta questionamentos bastante válidos e cases interessantes. O mundo não sabe falar a linguagem dos riscos de forma adequada, e todos deveriam estudar mais o assunto.
Um exemplo final. Risco é diferente de incerteza. Para mensurar o risco (exemplo, risco de perder na loteria), tenho que ter um alto grau de certeza. Por outro lado, podemos estar despreocupados com o risco de algo incerto (digamos, uma epidemia mundial), até que, finalmente, esta acontece.
Agradecimento ao amigo Flávio Deganutti por me emprestar o livro e pelas discussões.
“O colapso das sociedades complexas”, de Joseph Tainter, sustenta que a complexidade tem um custo orgânico. Sociedades complexas demais podem implodir, por não ter energia suficiente para sustentar tal organização.
O case ilustrativo é o do Império Romano, que cresceu adquirindo outros reinos ao redor, até chegar num ponto em que sustentar o aparato militar e administrativo se tornou um fardo tão pesado que o deixou vulnerável a ataques.
O crescimento das sociedades
As sociedades antigas eram muito simples, pequenas, com
poucas distinções além das biológicas (como idades e sexo). Tais sociedades
tinham poucas dezenas de profissões. Para efeito de comparação, estima-se que
atualmente haja de 10 a 20 mil profissões.
O colapso é uma simplificação abrupta da sociedade.
A complexidade
A complexidade se manifesta através da criação de controles e estruturas para fazer a vida mais simples. Deste ponto de vista, a complexidade serve para simplificar.
Por que as sociedades ficam mais complexas?
Porque é isto bom para resolver problemas igualmente complexos.
Ex. O ataque terrorista de 11/09/2001 gerou mais controle, mais regulação, mais agências; tudo isso pago com impostos da sociedade, ou o tempo e energia de pessoas, com mais filas e burocracia nos aeroportos.
Exemplo de sociedades estudadas pelo Dr. Tainter:
Império romano
Império Hitita da Anatólia
Império Zhou do sudoeste (China)
Reino antigo do Egito
Povos do norte do México
e muitos outros
A Complexidade é uma função econômica
A complexidade não é gratuita. Ela tem um custo metabólico,
em analogia aos corpos de animais. Um ser humano tem complexidade e custo
metabólica infinitamente maior do que uma mosca, por exemplo.
No caso da sociedade, tais custos se traduzem em tempo,
dinheiro e energia.
Antes da era dos combustíveis fósseis, as pessoas tinham que
trabalhar mais para sustentar o acréscimo de custos.
O ciclo do aumento da complexidade:
– Traz benefícios,
– Aumenta custos,
– A cada ciclo, há diminuição do retorno.
Espiral energia-complexidade
A complexidade precisa de energia.
Energia sobrando leva a mais complexidade, dada a
inventividade do ser humano.
Caso: o colapso do Império Romano
O Império Romano cresceu conquistando províncias, sustentada por pilhagem, taxas e pressão inflacionária.
Pilhagem é a captura da energia do passado, na forma de
metais, arte, armas, pessoas etc. Porém, essa captura é de curto prazo, só pode
ser feita uma vez no mesmo local. A conquista gera riqueza, entretanto é
necessário conquistar mais para continuar crescendo.
Para manter os territórios e conquistar outros, é necessário
um crescente aparato militar e administrativo. Isso leva a um aumento do
exército e de funcionários.
Na época de Roma, a fonte definitiva de energia era o Sol.
A agricultura tem o seu limite de produção, e fazendeiros
produzem pouco excesso per capita.
Outra fonte de recursos eram os altos impostos, tão altos
que os fazendeiros não eram capazes de acumular reservas – então não podiam
suportar grandes famílias.
Quando uma família não conseguia pagar as altas taxas,
outras famílias tinham que compensar. Havia casos de vilas inteiras que tinham
que pagar por outras.
Uma terceira fonte de financiamento era a inflação. A
hiperinflação (tão conhecida dos brasileiros pré-plano Real) mostrou suas garras
em Roma, corroendo o valor do denário da população. A inflação é uma forma de
assaltar a carteira das pessoas sem apontar uma arma em suas cabeças, mas com
efeitos igualmente perversos.
Declínio populacional, pragas, crises, ataques externos e
guerra civil constante levaram Roma à bancarrota.
A complexidade causa danos sutis, imprevisíveis e
cumulativos.
A sociedade pode ser destruída pelo custo de se sustentar.
Conseguiremos superar limites?
Passamos milhares de anos sem inovar, ou com pouquíssimas
inovações.
Mas, no mundo atual, a inovação está presente, e é central
no dia-a-dia.
Achamos que sempre podemos superar os limites a partir da
inovação. Será a tecnologia suficiente?
Palavras do pesquisador Nicholas Rescher: a pesquisa está se
tornando cada vez mais complexa, com retornos decrescentes.
Uma taxa constante de inovação precisa de mais e mais
recursos.
As descobertas fáceis, o fruto baixo a ser colhido, já o
foi. Antigamente, o inventor era um pensador solitário que fazia descobertas na
garagem de casa. Hoje, os times de pesquisa são enormes e multidisciplinares,
exigindo equipamentos e instalações de milhões de dólares.
Em saúde, em especial remédios, há custos cada vez maiores
para retornos menores.
Gastos militares crescem em equipamentos cada vez mais
sofisticados.
É possível que o planeta Terra inteiro tenha se tornado algo comparável com o Império Romano… Devemos tomar cuidado para a complexidade não nos engolir.
A matemática contém algumas afirmações que são extremamente fáceis de serem formuladas, mas extremamente difíceis de serem resolvidas.
A conjectura de Goldbach é um caso desses:
“Qualquer número par pode ser descrito como a soma de dois números primos”.
Números primos são aqueles que são indivisíveis por outros números, como 2, 3, 5, 7, 11. Alguns exemplos da conjectura.
4=2+2
6=3+3
8=3+5
10=3+7
100=53+47
É uma “conjectura” porque ninguém conseguiu prova-lo, em quase 300 anos. E a sua fama provém não da conjectura em si, ou da utilidade prática, mas porque grandes mentes já tentaram prova-la e não conseguiram.
Uma coisa irônica nisto é que o computador pode ajudar a provar alguns teoremas, mas o melhor computador do mundo não vai ajudar nada em outros. Isto porque as provas da matemática requerem que a validade seja para todos os números. Sempre vai haver um número impossível de ser computado (seja ele 10^100000, 10^1000000000). É possível escrever programas de computador para testar números muito grandes, mas não para testar todos os números. O computador serve mais para “desprovar”, no caso de achar um número que não atende a conjectura, ou para aumentar os indícios de que o caminho está correto, mas não para provar.
