A querida leitora é candidata a um ótimo emprego. A empresa faz uma série de perguntas às quais a leitora deve responder de forma binária: Sim ou Não. A partir dessas respostas, o contratante decide sobre a sua contratação, também de forma binária.

Infelizmente, a resposta é negativa! E a leitora se questiona —de maneira hipotética, claro!— se não teria sido melhor dar "um jeitinho" em algumas respostas... Quantas mentirinhas teriam sido suficientes para que o resultado passasse a ser positivo?

Este tipo de procedimento é exemplo do que os matemáticos e cientistas da computação chamam "função de Boole", que é uma regra qualquer para transformar um certo número de dados binários (as respostas da leitora) em um resultado também binário (a decisão sobre contratá-la). O exemplo interessante mais simples é a "negação", que usa apenas um dado: se o seu valor é Sim, o resultado é Não; e se o valor do dado é Não, o resultado é Sim.

A denominação homenageia o matemático e filósofo inglês George Boole (1815-1864), autor do livro "As Leis do Pensamento", publicado em 1854. Nele, Boole introduziu o que hoje chamamos "álgebra de Boole", que é uma formulação matemática da lógica. Nesta teoria, os valores binários podem ser Sim e Não, como no nosso exemplo, ou Verdadeiro e Falso, ou até 1 e 0, que são os favoritos da minha turma: não faz diferença.

Não é uma área especialmente difícil da matemática: estudei os seus fundamentos no início do ensino médio. Mas dizer que é extremamente importante, útil e atual seria pouco: tudo o que os computadores eletrônicos fazem é calcular funções de Boole e, por isso, a álgebra de Boole está na base de toda a ciência e tecnologia da computação.

O número de mudanças nos dados (as mentirinhas hipotéticas da leitora) suficiente para inverter o resultado é chamado "sensibilidade" da função de Boole. É uma maneira de medir quão complexa é a função. Há outras, mas os cientistas da computação mostraram que todas as demais dão resultados semelhantes: a única que resistia a se encaixar nessa teoria era, precisamente, a sensibilidade.

Em 1992, os pesquisadores Noam Nisan (Israel) e Mario Szegedy (Estados Unidos) conjecturaram que a sensibilidade também concorda com as demais medidas de complexidade, mas durante quase três décadas ninguém conseguiu provar esse fato.

Até que em 2019... (continua na próxima semana).