Uma Introdução à Teoria da Computabilidade e Complexidade

Alguma vez você já se perguntou: Qual é exatamente o dispositivo em que você está lendo este artigo? O que é um computador?

A ciência computacional remonta a muito antes de esses dispositivos de computação modernos serem imaginados. Em uma indústria onde as perguntas mais frequentes giram em torno de linguagens de programação, frameworks e bibliotecas, muitas vezes não damos valor aos conceitos fundamentais que fazem um computador funcionar.

Mas esses computadores, que parecem possuir um potencial infinito, eles têm alguma limitação? Existem problemas que os computadores não podem ser usados ​​para resolver?

Neste artigo, abordaremos essas questões afastando-nos das particularidades das linguagens de programação e arquiteturas de computador. Ao entender o poder e as limitações dos computadores e algoritmos, podemos melhorar a maneira como pensamos e raciocinamos melhor sobre diferentes estratégias.

A visão abstrata da computação produz resultados que resistiram ao teste do tempo, sendo tão valiosos para nós hoje quanto eram quando desenvolvidos inicialmente na década de 1970.

Computabilidade

O que é um computador? O que é um problema?

Na escola, muitas vezes nos ensinam um modelo mental de problemas e funções mais ou menos assim:

Uma função é um procedimento que você aplica a uma entrada x para encontrar uma saída f(x).

Acontece que a definição matemática é diferente:

Uma função é um conjunto de pares ordenados tal que o primeiro elemento de cada par é de um conjunto X (chamado de domínio), o segundo elemento de cada par é de um conjunto Y (chamado de contradomínio ou intervalo) e cada elemento de o domínio é emparelhado com exatamente um elemento do intervalo.

Isso foi bastante bocado. Mas o que exatamente aquilo significa?

Esta definição nos diz que um computador é uma máquina para computar funções.

Por quê?

Porque os computadores transformam entradas arbitrárias em alguma saída. Em outras palavras, eles resolvem problemas. As duas definições de funções, aquela com a qual estamos tão familiarizados e a formal, coincidem para muitos propósitos práticos.

No entanto, a definição matemática nos permite chegar a conclusões interessantes, como a existência de funções incomputáveis ​​(ou seja, problemas insolúveis):

Porque nem toda função pode ser descrita como um algoritmo.

Regras do jogo

Para ajudar a construir nossos argumentos, vamos imaginar computadores como máquinas recebendo alguma entrada, executando uma sequência de operações e, depois de algum tempo, fornecendo alguma saída.

Chamaremos a entrada de alfabeto da máquina; isto é, um conjunto de cadeias de caracteres de algum conjunto finito. Por exemplo, o alfabeto da máquina pode ser binário (0s e 1s) ou pode ser o conjunto de caracteres ASCII. Qualquer sequência finita de caracteres é uma string — por exemplo, “0110”.

Além disso, representaremos a saída de uma máquina como uma decisão binária de aceitar-rejeitar, entregue assim que a máquina (espero) terminar sua computação. Essa abstração se encaixa bem com a definição matemática de funções anterior.

Dados esses parâmetros, é importante caracterizar mais um tipo: uma coleção de strings. Talvez nos preocupemos com o conjunto de strings que alguma máquina aceita, ou talvez estejamos construindo uma máquina que aceita strings em um determinado conjunto e não em outros, ou talvez estejamos perguntando se é possível projetar uma máquina que aceite tudo em algum determinado conjunto e nenhum outro.

Em todos esses casos, um conjunto de strings é chamado de linguagem – por exemplo, o conjunto de todas as strings binárias que representam números pares ou o conjunto de strings que possuem um número par de caracteres. Acontece que linguagens, como números, podem ser operadas com operadores como concatenação, união, interseção e similares.

Um operador importante é o operador estrela de Kleene que também é usado com expressões regulares. Isso pode ser pensado como a união de todos os poderes possíveis da linguagem. Por exemplo, se nossa linguagem A é o conjunto de strings { '01', '1' }, então um membro de A* é a string '0101111'.

Contabilidade

A última peça do quebra-cabeça antes de provarmos nossa afirmação de que nem todas as funções são computáveis ​​é o conceito de contabilidade. Intuitivamente, nossa prova mostrará que existem mais linguagens; ou seja, mais problemas do que programas possíveis para resolvê-los. Isso funciona porque a questão de saber se uma string pertence a um idioma (Sim/Não) é um problema.

Mais precisamente, nossa prova afirma que o conjunto de programas possíveis é infinito contável, enquanto o conjunto de linguagens sobre um alfabeto é infinito incontável.

Neste ponto, você pode estar pensando: “O infinito é uma ideia bastante estranha por si só; agora eu tenho que lidar com dois deles!”

Bem, não é tão ruim. Um conjunto infinito contável é aquele que pode ser enumerado. É possível dizer que este é o primeiro elemento, este é o segundo elemento, e assim por diante, eventualmente atribuindo um número a cada elemento do conjunto. Pegue o conjunto de números pares, por exemplo. Podemos dizer que 2 é o primeiro, 4 o segundo, 6 o terceiro e assim por diante. Tais conjuntos são infinitos contáveis ​​ou contáveis.

No entanto, com alguns conjuntos, como os números reais, não importa o quão inteligente você seja; simplesmente não há enumeração. Esses conjuntos são incontavelmente infinitos ou incontáveis.

Muitos programas incontáveis

Primeiro, queremos mostrar que o conjunto de programas de computador é contável. Para nossos propósitos, fazemos isso observando que o conjunto de todas as strings em um alfabeto finito é contável. Isso funciona porque os programas de computador são strings finitas.

A prova é direta e não abordamos os detalhes aqui. A principal conclusão é que existem tantos programas de computador quanto, digamos, números naturais.

Reiterar:

O conjunto de todas as cadeias de qualquer alfabeto (por exemplo, conjunto de todos os programas de computador) é contável.

Incontáveis ​​Muitos Idiomas

Dada essa conclusão, e os subconjuntos dessas strings? Perguntado de outra forma, e quanto ao conjunto de todos os idiomas? Acontece que este conjunto é incontável.

O conjunto de todas as línguas sobre qualquer alfabeto é incontável.

Mais uma vez, não cobrimos a prova aqui.

Consequências

Embora possam não ser imediatamente aparentes, as consequências da incontabilidade das linguagens e da contabilidade do conjunto de todos os programas de computador são profundas.

Por quê?

Suponha que A seja o conjunto de caracteres ASCII; Caracteres ASCII são apenas aqueles necessários para compor um programa de computador. Podemos ver que o conjunto de strings que representam, digamos, programas JavaScript, é um subconjunto de A* (aqui, * é o operador estrela de Kleene). A escolha do JavaScript é arbitrária. Como esse conjunto de programas é um subconjunto de um conjunto contável, temos que o conjunto de programas JavaScript é contável.

Além disso, vamos considerar que para qualquer linguagem L , podemos definir alguma função f que resulta em 1 se alguma string x estiver em L e 0 caso contrário. Todas essas funções são distintas. Como existe uma correspondência 1:1 com o conjunto de todas as linguagens e como o conjunto de todas as linguagens é incontável, temos que o conjunto de todas essas funções é incontável.

Aqui está o ponto profundo:

Como o conjunto de todos os programas válidos é contável, mas o conjunto de funções não, então deve haver algumas funções para as quais simplesmente não podemos escrever programas.

Ainda não sabemos como são essas funções ou problemas, mas sabemos que existem. Esta é uma percepção humilhante, porque existem alguns problemas para os quais não há solução. Consideramos os computadores extremamente poderosos e capazes, mas algumas coisas estão fora de seu alcance.

Agora, a pergunta se torna: “Como são esses problemas?” Antes de continuarmos descrevendo tais problemas, temos que primeiro modelar a computação de forma generalizada.

Máquinas de Turing

Um dos primeiros modelos matemáticos de um computador foi desenvolvido por Alan Turing. Esse modelo, chamado de máquina de Turing, é um dispositivo extremamente simples que captura completamente nossa noção de computabilidade.

A entrada para a máquina é uma fita na qual a entrada foi gravada. Usando um cabeçote de leitura/gravação, a máquina transforma entrada em saída por meio de uma série de etapas. Em cada etapa, é tomada uma decisão sobre se e o que gravar na fita e se deve movê-la para a direita ou para a esquerda. Esta decisão é baseada em exatamente duas coisas:

• O símbolo atual sob a cabeça e

• O estado interno da máquina, que também é atualizado à medida que o símbolo é escrito

É isso.

Universalidade

Em 1926, Alan Turing não apenas desenvolveu a máquina de Turing, mas também teve vários outros insights importantes sobre a natureza da computação quando escreveu seu famoso artigo, “On Computable Numbers”. Ele percebeu que um programa de computador em si poderia ser considerado entrada para um computador. Com esse ponto de vista, ele teve a bela ideia de que uma máquina de Turing poderia simular ou executar essa entrada.

Embora consideremos essas ideias como garantidas hoje, na época de Turing, a ideia de uma máquina tão universal foi o grande avanço que permitiu a Turing desenvolver problemas insolúveis.

Tese de Church-Turing

Antes de continuarmos, vamos examinar um ponto importante: sabemos que a máquina de Turing é um modelo de computação, mas é geral o suficiente? Para responder a essa pergunta, nos voltamos para a Tese de Church-Turing, que dá credibilidade à seguinte afirmação:

Tudo computável é computável por uma máquina de Turing.

Enquanto Turing desenvolveu a máquina de Turing como modelo de computação, Alonzo Church também desenvolveu um modelo de computação conhecido como cálculo lambda. Esses modelos são poderosos, porque descrevem a computação e o fazem de maneira igual a qualquer um dos computadores atuais ou a qualquer computador de todos os tempos. Isso significa que podemos usar uma máquina de Turing para descrever os problemas insolúveis que buscamos, sabendo que nossas descobertas se aplicariam a todos os computadores possíveis do passado, presente e além.

Reconhecimento e Decidibilidade

Temos que cobrir um pouco mais de pano de fundo antes de descrevermos concretamente um problema insolúvel, ou seja, os conceitos de reconhecedores de linguagem e decisores de linguagem.

Uma linguagem é reconhecível se houver uma máquina de Turing que a reconheça.

e

Uma linguagem é decidível se houver uma máquina de Turing que a decida.

Para ser um reconhecedor de uma linguagem, uma máquina de Turing deve aceitar todas as strings da linguagem e não deve aceitar nada que não esteja na linguagem. Ele pode rejeitar ou fazer um loop em tais strings. Para ser um decisor, uma máquina de Turing deve sempre parar em sua entrada aceitando ou rejeitando.

Aqui, a ideia de parar na entrada é crítica. Na verdade, vemos que os decisores são mais poderosos que os reconhecedores. Além disso, um problema é solucionável, ou dito de outra forma, uma função é decidível somente se existir uma máquina de Turing que decida a linguagem descrita pela função.

Indecidibilidade

Se você já escreveu um programa de computador, certamente deve conhecer a sensação de estar sentado ali apenas observando o computador girar suas rodas quando o programa é executado. Você não sabe se o programa está demorando muito ou se há algum erro no código causando um loop infinito. Você pode até ter se perguntado por que o compilador não verifica o código para ver se ele pararia ou faria um loop para sempre quando executado.

O compilador não tem essa verificação porque simplesmente não pode ser feito. Não é que os engenheiros de compiladores não sejam inteligentes o suficiente ou não tenham recursos; é simplesmente impossível verificar um programa de computador arbitrário para determinar se ele para.

Podemos provar isso usando a máquina de Turing. As máquinas de Turing podem ser descritas como strings, portanto, há um número contável delas. Suponha que M ₁ , M ₂ e assim por diante constituam o conjunto de todas as máquinas de Turing. Vamos definir a seguinte função:

Aqui, <M> é a sintaxe para “codificação de string de M”, e esta função representa o problema de produzir 1 se M _i parar aceitando M _j como entrada e saída 0 caso contrário. Observe que M _i deve parar (ou seja, ser um decisor). Isso é necessário, pois desejamos descrever uma função indecidível (ou seja, um problema insolúvel).

Agora, vamos definir também uma linguagem L que consiste em codificações de strings de máquinas de Turing que NÃO aceitam suas próprias descrições:

Por exemplo, alguma máquina M ₁ pode emitir 0 na entrada <M ₁ > enquanto outra máquina M ₂ pode emitir 1 na entrada <M ₂ >. Para provar que essa linguagem é indecidível, perguntamos o que M _L , a máquina que decide a linguagem L, faz quando recebe sua própria descrição <M _L > como entrada. Existem duas possibilidades:

M _L aceita <M _L >

ou

_{ML rejeita <M L >}

Se M _L aceita sua própria codificação, então isso significa que <M _L > não está na linguagem L; no entanto, se esse fosse o caso, _ML não deveria ter aceitado sua codificação em primeiro lugar. Por outro lado, se ML não aceita sua própria codificação, então < _ML > está na linguagem _L , então _ML deveria ter aceitado sua codificação de string.

Em ambos os casos, temos um paradoxo, ou em termos matemáticos, uma contradição, provando que a linguagem L é indecidível; assim, descrevemos nosso primeiro problema insolúvel.

Problema de parada

Embora o problema que acabamos de descrever possa não parecer relevante, ele pode ser reduzido a outros problemas insolúveis de importância prática, principalmente o problema da parada:

A linguagem das codificações das máquinas de Turing que param na string vazia.

O problema da parada se aplica à questão de por que os compiladores não podem detectar loops infinitos anteriores. Se não podemos determinar se um programa termina na string vazia, como poderíamos determinar se sua execução resultaria em um loop infinito?

Neste ponto, pode parecer que apenas balançamos nossas mãos para chegar a uma conclusão simples; no entanto, percebemos que nenhuma máquina de Turing pode dizer se um programa de computador irá parar ou permanecer em um loop para sempre. Este é um problema importante com aplicações práticas, e não pode ser resolvido em uma máquina de Turing ou qualquer outro tipo de computador. Um iPhone não pode resolver esse problema. Um desktop com muitos núcleos não pode resolver esse problema. A nuvem não pode resolver esse problema. Mesmo se alguém inventasse um computador quântico, ele ainda não seria capaz de resolver o problema da parada.

Resumo

Em nosso exame da teoria da computabilidade, vimos como existem muitas funções que não são computáveis ​​em nenhum sentido comum da palavra por um argumento de contagem. Definimos precisamente o que queremos dizer com computação, voltando à inspiração de Turing de sua própria experiência com caneta e papel para formalizar a máquina de Turing. Vimos como esse modelo pode calcular qualquer coisa que qualquer computador hoje ou imaginado para amanhã pode, e percebemos uma classe de problemas que não são computáveis.

Ainda assim, a computabilidade tem uma desvantagem. Só porque podemos resolver um problema não significa que podemos resolvê-lo rapidamente. Afinal, de que serve um computador se sua computação não terminar antes que o sol se transforme em nova em nós dezenas de milhões de anos no futuro?

Deixando para trás as funções e linguagens computáveis, discutimos agora a complexidade computacional, levantando a computação eficiente e o famoso problema P vs. NP.

Complexidade

Lento vs. Rápido

Os cientistas da computação reconhecem uma variedade de classes de problemas, e duas classes com as quais nos preocupamos incluem problemas que os computadores podem resolver de forma rápida ou eficiente, conhecidos como P , e problemas cujas soluções podem ser verificadas rapidamente, mas não podem ser obtidas rapidamente, conhecidas como NP .

Por exemplo, suponha que você seja responsável pelo desenvolvimento de algoritmos para um serviço de namoro online e alguém faça a pergunta: “Todo mundo pode marcar um encontro?” A resposta se resume a emparelhar indivíduos compatíveis de modo que todos estejam emparelhados. Acontece que existem algoritmos eficientes para resolver esse problema. Este problema está no conjunto P .

Bem, e se quiséssemos identificar a maior panelinha entre nossos usuários? Por clique, queremos dizer a maior rede de indivíduos que são todos compatíveis uns com os outros. Quando a contagem de usuários é baixa, esse problema pode ser resolvido rapidamente. Podemos identificar facilmente, digamos, uma panelinha com 3 usuários. À medida que começamos a procurar panelinhas maiores, no entanto, o problema se torna cada vez mais difícil de resolver. Este problema está no conjunto NP .

Definições formais

P é o conjunto de problemas que são solucionáveis ​​em tempo polinomial. Ou seja, o número de etapas computacionais é limitado por uma função polinomial em relação ao tamanho do problema. Sabemos que o “todo mundo pode conseguir um encontro?” A questão, também conhecida como problema de emparelhamento bipartido, está em P .

NP é o conjunto de problemas que são verificáveis ​​em tempo polinomial. Isso inclui todos os problemas em P, é claro; no entanto, não sabemos se essa contenção é rigorosa. Sabemos de problemas que são verificáveis ​​com eficiência, mas não solucionáveis ​​com eficiência, mas não sabemos se o problema é realmente intratável. O problema da clique é um desses problemas. Sabemos que podemos verificar a solução com eficiência, mas não sabemos ao certo se podemos resolver o problema com eficiência.

Por fim, NP-completo é o conjunto de problemas que são os problemas mais difíceis em NP . Eles são referidos como os mais difíceis porque qualquer problema em NP pode ser eficientemente transformado em NPC . Como resultado, se alguém identificasse uma solução eficiente para um problema em NPC , então toda a classe de NP seria absorvida por P . O problema do clique também está no NPC .

Assim, chegamos ao problema de P vs. NP . Muitos cientistas da computação e matemáticos acreditam fortemente que P e NP não são iguais. Se fossem, as implicações seriam além de profundas. Grande parte da infraestrutura digital de hoje depende do fato de que existem problemas em NP que não estão em P . Se não fosse esse o caso, os métodos criptográficos, por exemplo, entrariam em colapso da noite para o dia, permitindo que uma pessoa que possui uma solução eficiente para um problema de NPC subverta até mesmo os protocolos de segurança mais rígidos.

Sutilezas de Tratabilidade

Para iniciantes em ciência da computação, a diferença entre os problemas de correspondência e clique pode não parecer grande coisa. De fato, a diferença entre um problema em P e um problema em NP pode ser muito sutil. Ser capaz de dizer a diferença é importante para qualquer pessoa que esteja projetando algoritmos no mundo real.

Considere o problema do caminho mais curto. Dados dois locais, o objetivo é identificar o caminho mais curto entre eles. Um iPhone calcula isso em questão de milissegundos. Este é um problema computacionalmente tratável.

Por outro lado, considere o problema do caixeiro viajante, onde o objetivo é visitar um subconjunto de destinos possíveis que terminam na origem, percorrendo a menor distância possível. Esse problema é semelhante ao problema do caminho mais curto, mas é NP-completo; também explica por que a logística da cadeia de suprimentos é uma indústria de bilhões de dólares.

Na verdade, podemos ser ainda mais sutis. Em vez de pedir o caminho mais curto (P), podemos pedir o caminho mais longo sem ciclos. Acontece que o problema do caminho mais longo também é NP-completo.

Existem muitos outros exemplos dessa distinção sutil, incluindo a identificação de coberturas de vértices em grafos bipartidos versus gerais ou a satisfação de fórmulas booleanas com dois versus três literais por cláusula. O ponto é que não é imediatamente óbvio se um problema está em P ou NP, e é por isso que a análise de tempo de execução é uma habilidade crítica. Se o algoritmo que se deve projetar é para um problema em P, então sabemos que existe uma solução eficiente. Se, por outro lado, o problema está em NP, então temos um argumento forte para argumentar contra a busca de uma solução, porque o algoritmo, geralmente, levaria muito tempo para resolver o problema.

Resumo

Neste exame de complexidade, definimos as classes de problemas P e NP. P representa informalmente problemas que podem ser resolvidos eficientemente por um computador, enquanto NP representa aqueles que são verificáveis ​​de forma eficiente.

Ninguém foi capaz de provar que P não é igual a NP. Se essas duas classes de problemas são equivalentes é conhecido como o problema P vs. NP, e é o problema aberto mais importante na ciência da computação teórica hoje, se não em toda a matemática. De fato, no ano 2000, o Clay Math Institute nomeou o problema P vs. NP como uma das sete questões abertas mais importantes da matemática e ofereceu uma recompensa de um milhão de dólares por uma prova que determinasse a solução para esse problema.

Conclusão

Neste artigo, mergulhamos nos domínios da computabilidade e da complexidade, respondendo a grandes perguntas como: “O que é um computador?” Embora os detalhes possam ser impressionantes, há vários pontos importantes que vale a pena lembrar:

• Existem algumas coisas que simplesmente não podem ser computadas, como o problema da parada.

• Existem algumas coisas que não podem ser computadas de forma eficiente, como os problemas no NPC.

Mais importante do que os detalhes são as maneiras de pensar sobre computação e problemas computacionais. Em nossa vida profissional e até mesmo em nosso dia a dia, podemos nos deparar com problemas nunca vistos antes, e podemos usar ferramentas e técnicas testadas e comprovadas para determinar o melhor curso de ação.

Leitura adicional no Blog da Toptal Engineering:

• Como abordar a escrita de um intérprete do zero