Prévia do material em texto

ANÁLISE DE 
ALGORITMOS
Thiago Nascimento Rodrigues
Computabilidade
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
  Reconhecer os aspectos fundamentais da computabilidade.
  Descrever o conceito de incomputabilidade.
  Identificar as principais classes de computabilidade.
Introdução
Resolver problemas de diferentes complexidades e tamanhos em um 
período viável constitui a essência dos algoritmos computacionais. No 
entanto, nem sempre um dado problema pode ser solucionado por 
meio de um procedimento composto por um número finito de passos. A 
identificação e a caracterização de cenários como esse são fundamentais 
para que estratégias adequadas possam ser empregadas na busca por 
uma solução de qualidade.
Neste capítulo, você vai conhecer os fundamentos relacionados ao 
conceito de problemas resolvíveis por um mecanismo computacional 
e vai aprender como categorizar problemas de acordo com as distintas 
classes de computabilidade. Além disso, noções de uma das questões 
mais importantes da computação, e que ainda permanece sem resposta, 
serão apresentadas.
1 Fundamentos de computabilidade
Diferentes algoritmos possuem uma ampla variedade de diferentes funções 
de complexidade de tempo, e a caracterização de quais dessas funções são 
“sufi cientemente efi cientes” e quais são “muito inefi cientes” sempre vai de-
pender do problema a ser resolvido. No contexto da computação, o conceito 
de problema está relacionado a uma questão geral que precisa ser respondida 
e que, comumente, possui vários parâmetros, ou variáveis livres, cujos valores 
não são especifi cados. Logo, um problema pode ser descrito por: 
1. uma descrição geral de todos seus parâmetros;
2. uma afirmação a respeito de qual propriedade a resposta, ou solução, 
deve satisfazer. 
De posse dessa definição, uma instância de um problema é obtida pela 
especificação de valores particulares para todos os parâmetros do problema. 
Uma maneira de se descrever como a solução para um dado problema pode ser 
obtida é apresentar um algoritmo para ele, ou seja, listar o conjunto de passos 
que levam à geração da solução. Um algoritmo é dito ser capaz de resolver 
um problema X se tal algoritmo pode ser aplicado a uma instância I de X e 
tem-se a garantia de que ele sempre produzirá uma solução para a instância 
I (GAREY; JOHNSON, 1979).
Para vários problemas encontrados na literatura científica, já foram pro-
postos algoritmos capazes de encontrar soluções em tempo polinomial, ou 
seja, dada uma entrada de tamanho n, o pior caso da complexidade de tempo 
é O(nk) para alguma constante k. Algoritmos que apresentam esse compor-
tamento assintótico são dito tratáveis. Embora diversas técnicas já tenham 
sido desenvolvidas para guiar a construção de algoritmos com essa ordem 
de eficiência, não é possível afirmar que exista uma metodologia geral para 
a obtenção de procedimentos computacionais eficientes para qualquer dado 
problema. Ao contrário, cada novo problema que surge apresenta, em geral, 
desafios desconhecidos e que exigem a proposição de novas estratégias para 
lidar com a dificuldade inerente a cada um (SEN; KUMAR, 2019). 
Na prática, existem problemas cujos únicos algoritmos capazes de solucioná-
-los demandam um tempo computacional inviável — à medida que o tamanho 
da entrada cresce, o tempo requerido para se resolver o problema cresce a 
uma taxa não polinomial (crescimento exponencial, fatorial, etc.). Problemas 
dessa natureza são ditos intratáveis.
Embora essas duas classes de problemas (tratáveis e intratáveis) apresen-
tem uma diferença determinante em relação à eficiência na obtenção de suas 
soluções, ainda assim problemas dessas duas categorias podem ser resolvidos 
por meio de algum algoritmo computacional. Essa condição os classifica como 
problemas computáveis. Outros sinônimos comuns para “computável” são 
“resolvível”, “decidível” e “recursivo” (IMMERMAN, 2015). A contrapar-
tida são problemas que não podem ser resolvidos por meio de um programa 
executado por computador. Esses são ditos problemas incomputáveis. O 
Quadro 1, a seguir, apresenta uma visão esquemática de como os problemas 
na computação podem ser classificados de acordo com a eficiência e a viabili-
dade de implementação computacional dos algoritmos capazes de resolvê-los.
Computabilidade2
Fonte: Adaptado de Princeton University (2020).
Problemas
tratáveis
Problemas 
intratáveis
Problemas 
incomputáveis
Descrição
Podem ser 
resolvidos 
eficientemente
Existem algoritmos 
para resolvê-los, 
mas demandam 
tempo inviável
Não podem ser resolvi-
dos por nenhum pro-
grama computacional
Computáveis 
na teoria
Sim Sim Não
Computáveis 
na prática
Sim Sim/Não Não
Exemplo
Rota mais curta 
em um mapa
Decriptação Encontrar todos os 
erros de um programa 
computacional
O Sim/Não marcado na classe dos problemas incomputáveis indica que, para certos problemas 
considerados intratáveis, não existe ainda uma prova formal de que são, de fato, intratáveis.
Quadro 1. As três maiores categorias de problemas computacionais
Embora o conceito de computabilidade esteja claro sob a perspectiva de 
ser resolvível por um algoritmo computacional, a busca por uma definição 
mais precisa e formal guiou os esforços de vários matemáticos ao longo dos 
anos. Por exemplo, Alonzo Church definiu o cálculo lambda; Kurt Gödel 
definiu funções recursivas; Stephen Kleene definiu sistemas formais; 
Markov definiu o que ficou conhecido como algoritmo de Markov; Emil 
Post e Alan Turing definiram máquinas abstratas agora conhecidas como 
máquinas de Post e máquinas de Turing. Todas esses formalismos foram 
propostos como mecanismos para expressar a noção de computabilidade 
com o devido rigor matemático. 
Surpreendentemente, todos esses modelos se mostraram exatamente equi-
valentes, isto é, qualquer problema computável no cálculo lambda é também 
computável por uma máquina de Turing e, da mesma forma, computável em 
qualquer outro desses sistemas computacionais. Depois que isso foi provado, 
Church expressou a crença de que a noção intuitiva de “princípio computável” 
é idêntica às noções precisas dos sistemas formais propostos. Essa crença, 
agora conhecida como Tese de Church-Turing, é uniformemente aceita pelos 
matemáticos (IMMERMAN, 2015).
3Computabilidade
Entre os modelos criados para a formalização de algoritmos, prova-
velmente o mais utilizado é a máquina de Turing, proposta em 1936. De 
acordo com Diverio e Menezes (2011), o trabalho de Turing foi o primeiro 
a identificar programas escritos para uma máquina computacional, com 
noções intuitivas do efetivamente computável. A ideia básica da máquina 
de Turing é a de um mecanismo empregado para a realização de cálculos e 
formado pelos seguintes componentes:
  uma fita de tamanho infinito usada para o armazenamento de 
informações;
  uma unidade de controle capaz de executar cálculos e dotada de um 
dispositivo (cabeça) para leitura e escrita de dados;
  um programa responsável pela definição dos comandos a serem exe-
cutados pela unidade de controle.
A Figura 1 ilustra como a máquina de Turing poderia ser representada 
de maneira esquemática. É importante observar que, nesse modelo, alguns 
símbolos são reservados para fins especiais. Esses são os casos dos marca-
dores de início da fita e do espaço em branco, que devem ser interpretados 
corretamente pela unidade de controle. Outra observação relevante é que a 
cabeça responsável pela leitura/escrita de dados pode ser mover em ambos 
os sentidos: para a direita ou para a esquerda. Logo, o programa que passa a 
compor a máquina determina o símbolo a ser gravado ou lido e o sentido de 
movimentação da unidade de controle. 
Figura 1. Representação da máquina de Turing.
Fonte: Adaptado de Lechenco (c2020).
Computabilidade4
Uma forma prática de se desenhar e simular a execução de máquinas de Turing é com 
o uso da ferramenta JFLAP, disponível para download na internet.
Outra característicada máquina de Turing é que ela possui um conjunto 
finito de Q estados. A unidade de controle da máquina contém um compo-
nente chamado de “registro”, que pode conter um único elemento de Q; esse 
é o “estado” da máquina naquele instante. É importante ressaltar que essa é 
a versão da máquina de Turing conhecida como determinística. Há a versão 
não determinística, que permite que o registro contenha múltiplos estados. 
Esse estado determina sua ação na próxima etapa computacional, que consiste 
nos seguintes passos: 
1. ler os símbolos nas células diretamente da fita; 
2. substituir cada símbolo por um novo símbolo (ele tem a opção de não 
alterar a fita, anotando novamente o símbolo antigo);
3. alterar seu registro interno para conter outro estado do conjunto finito 
Q (ele tem a opção de não alterar seu estado, escolhendo o estado 
antigo novamente);
4. mover, a cada cabeça, uma célula para a esquerda ou para a direita. 
Assim, conforme apresentado por Arora e Barak (2007), uma máquina de 
Turing M pode ser formalmente representada por uma tupla (Γ, Q, δ) contendo:
  Um conjunto Γ de símbolos que a fita de comprimento infinito pode 
conter. Assume-se que Γ contém os seguinte símbolos especiais: um 
símbolo de espaço em branco denotado por Δ, um de início denotado 
por ► e os números 0 e 1. Logo, Γ é chamado de alfabeto de M.
  Um conjunto Q de estados possíveis que podem ser registrados em 
M. Assume-se que Q contém um estado inicial denotado por q0 e um 
estado de parada denotado por qf.
  Uma função δ: Q × Γ → Q × Γ × { E, P, D } descreve a regra que M 
usa para executar cada passo. Essa função é chamada de função de 
transição de M. O conjunto { E, P, D } indica os movimentos possíveis 
que a cabeça de leitura pode executar: E (mover para esquerda), D 
(mover para direita) e P (permanecer na posição).
5Computabilidade
Existem inúmeras variações quanto à definição da máquina de Turing. Em geral, essas 
apresentações alternativas do modelo não afetam seu poder computacional. Na 
prática, as principais modificações estão relacionadas às características da fita e ao 
movimento da cabeça de leitura/escrita. Por exemplo, alguns modelos não consideram 
um marcador de início da fita, enquanto outros consideram uma fita infinita em ambos 
os lados. Além disso, há definições que tratam a cabeça de leitura/escrita como não 
sendo móvel e outras, ainda, que introduzem o conceito de estado final de rejeição 
(DIVERIO; MENEZES, 2011).
Considerando essa definição formal, se a máquina estiver no estado q Є Q 
e σk corresponder ao símbolo que está sendo lido atualmente na fita e δ(q, σk) = 
(q’, σk’, z), onde z Є {E, P, D}, então, no próximo passo, o símbolo σk na fita será 
substituído pelo símbolos σk’. Além disso, a máquina estará no estado q’ e a cabeça 
de leitura/escrita se moverá para a esquerda ou para a direita, ou permanecerá na 
posição, conforme indicado por z. No caso de a máquina tentar se mover para a 
esquerda a partir da posição mais à esquerda da fita, ela permanecerá no lugar.
Sempre que a máquina de Turing vai iniciar a computação de uma entrada 
informada, a primeira posição da fita é inicializada com o símbolo de início 
►, e todas as demais posições recebem o símbolo Δ, de espaço em branco. 
Assim, a fita contém inicialmente o símbolo de início ► e uma sequência 
finita de caracteres que não são espaços em branco: a entrada. As demais 
células da fita contém o símbolo de espaço em branco. A cabeça de leitura 
começa a partir da extremidade esquerda da fita, e a máquina está em seu 
estado inicial especial q0. Isso é chamado de configuração inicial de M para 
uma dada entrada x. Cada etapa de cálculo é realizada aplicando-se a função 
δ como descrito acima. O estado de parada especial qf possui a propriedade de 
que, uma vez que a máquina esteja em qf, a função de transição δ não permite 
que fita continue sendo modificada ou M mude de estado. Claramente, se a 
máquina entrar no estado qf, ela será interrompida. 
É importante notar que apenas símbolos pertencentes ao alfabeto da má-
quina de Turing estão sendo considerados. Sob a óptica da teoria da complexi-
dade, em geral o interesse é por máquinas que param para cada entrada x em 
um número finito de etapas. O exemplo a seguir apresenta uma máquina de 
Turing que escreve o valor zero nas duas últimas posições de uma sequência 
de 0’s e 1’s (GAREY; JOHNSON, 1979). Nesse exemplo, a função de transição 
é representada de duas maneiras distintas, mas equivalentes.
Computabilidade6
Seja a seguinte máquina de Turing Γ = { 0, 1, ►, Δ }, Q = { q0, q1, q2, qf } e δ é dada pelo 
seguinte conjunto de regra:
(q0, ►) → (q0, ►, D)
(q0, 0) → (q0, 0, D)
(q0, 1) → (q0, 1, D)
(q0, Δ) → (q1, Δ, E)
(q1, 0) → (q2, 0, E)
(q1, 1) → (q2, 0, E)
(q2, 0) → (q3, 0, E)
(q2, 1) → (q3, 0, E)
Outra maneira de apresentar a função δ é por meio de uma tabela de regras, como segue.
q 0 1 ► Δ
q0 (q0, 0, D) (q0, 1, D) (q0, ►, D) (q1, Δ, E)
q1 (q2, 0, E) (q2, 0, E) — —
q2 (qf, 0, P) (qf, 0, P) — —
Essa máquina de Turing percorre qualquer sequência, passada como entrada, de 0’s 
e 1’s, cujo comprimento seja maior ou igual a 2, e escreve o valor zero nas duas últimas 
posições da sequência. Por exemplo, se uma sequência w = 101101 for informada, o 
valor retornado pela máquina será um w’ = 101100.
Embora o modelo da máquina de Turing constitua um formalismo simples 
e preciso para a representação de algoritmos e, consequentemente, para a defi-
nição da computabilidade de um dado problema, sua generalidade permanece 
uma questão em aberto até hoje. Essa condição é conhecida como a Tese de 
Church-Turing e propõe a seguinte hipótese: 
Um problema pode ser resolvido por um algoritmo se, e 
somente se, ele pode ser resolvido por uma máquina de Turing.
7Computabilidade
Em outras palavras, a tese sugere que qualquer função que pode ser com-
putada por um processo mecânico pode ser computada por uma máquina de 
Turing. Ambas as formulações, que são equivalentes, continuam sendo apenas 
teses, uma vez que nenhuma prova formal de sua veracidade foi encontrada. 
Da mesma forma, não se identificou qualquer contraexemplo que prove a 
falsidade da tese. Logo, ela permanece passível de ser provada como falsa ou 
verdadeira (HOPCROFT; MOTWANI; ULLMAN, 2007).
2 Incomputabilidade
Vários são os problemas (ou funções) que são decidíveis (ou computáveis), o 
que signifi ca que existe algum algoritmo que calcula uma resposta (ou saída) 
para qualquer instância do problema (ou para qualquer entrada da função) 
em um número fi nito de etapas simples. Por outro lado, também existem 
problemas e funções que são indecidíveis (ou incomputáveis), signifi cando 
que não existe um algoritmo que possa calcular uma resposta (ou saída) para 
todas as entradas em um número fi nito de passos. Nesse contexto, indecidível 
signifi ca, simplesmente, incomputável dentro do escopo de um problema de 
decisão, cuja resposta (ou saída) é “sim” ou “não”. 
Um exemplo de problema dessa classe é conhecido como o problema da 
totalidade. Ele consiste em decidir se uma máquina de Turing arbitrária é 
interrompida para qualquer entrada passada para ela. Se existir um algoritmo 
capaz de tomar essa decisão, então é dito que ele calcula uma “função total”. 
Esse problema é equivalente ao problema de determinar se um programa pode 
ou não entrar em um laço infinito para qualquer entrada informada. Da mesma 
forma, o fato de o problema da totalidade ser indecidível significa que não 
é possível escrever um programa que seja capaz de encontrar qualquer laço 
infinito em qualquer programa.
Outro problema comprovadamente indecidível é conhecido como o pro-
blema da equivalência. Ele envolve decidir se duas máquinas de Turing 
aceitam a mesma linguagem. Isso é equivalente ao problema de decidir se dois 
programas calculam a mesma saída para cada qualquer entrada passada como 
parâmetro. Na prática, o fato de o problema da equivalência ser indecidível 
significa que, embora a fase de otimizaçãode código de um compilador possa 
melhorar o desempenho de um programa, ela nunca garante a localização 
da versão otimizada mais eficiente do programa. Logo, pode haver versões 
potencialmente aprimoradas do programa que um compilador não é capaz de 
determinar se são equivalentes (HANSEN, 2017).
Computabilidade8
Uma linguagem corresponde ao conjunto de todas as palavras que podem ser constru-
ídas a partir de um conjunto de caracteres denominado alfabeto. Uma maneira comum 
de se descrever uma linguagem é por meio da notação de construção de conjuntos: 
{ w | alguma regra sobre w }
Essa expressão é lida como “o conjunto de palavras w tais que (alguma regra é dita 
sobre w)”. Alguns exemplos de linguagem são: 
1. { w | w consiste de um número igual de 0’s e 1’s };
2. { w | w é um número inteiro binário que é primo };
3. { w | w é um programa Java sintaticamente correto }.
Também é comum substituir w por alguma expressão com parâmetros e descrever 
a regra da linguagem pela definição de condições para os parâmetros. Um exemplo 
é a linguagem { 0n1n | n ≥ 1 }. Ela deve ser entendida como o conjunto de palavras 
compostas por uma sequência de n 0’s seguida por uma sequência de de n 1’s, onde 
n deve ser maior ou igual a um (HOPCROFT; MOTWANI; ULLMAN, 2007).
Um terceiro exemplo de problema que é reconhecidamente indecidível, ou 
incomputável, é denominado como problema da parada. Ele foi proposto 
por Alan Turing em 1936, no mesmo trabalho em que o conceito de máquinas 
computáveis foi apresentado. Sua formulação é bem simples: o problema de 
determinar se a execução de um programa termina ou não termina (para ou 
não para) é indecidível. Em outras palavras, uma função que receba como 
parâmetros um programa e as entradas por ele requeridas não é computável 
por qualquer máquina de Turing. Para que a indecidibilidade do problema 
fique bem clara, seja uma linguagem de programação qualquer dotada das 
seguintes instruções:
x := E
se B então P senão Q
enquanto B faça P
Essas são instruções de atribuição padrão, comandos condicionais e de laço 
encontrados na maioria das linguagens de programação modernas (exceto por 
questões de diferenças sintáticas). Na declaração de atribuição, x é uma variável 
9Computabilidade
de programa e E é uma expressão do mesmo tipo que x. Nos próximos dois, B 
é uma expressão booleana e P e Q são instruções de programação quaisquer. Os 
dois valores booleanos são V (verdadeiro) e F (falso). Por expressão booleana, 
deve-se entender uma expressão cujo tipo geral é booleano. Além disso, qualquer 
fragmento de programa (declaração ou expressão) será considerado um “programa”.
Tendo estabelecido as definições acima, seja uma função h: P → B, onde P é um 
tipo de dado que representa um programa e B é um tipo de dado booleano. Então, 
quando h é aplicada a um programa que termina, o resultado retornado por h é V, 
e quando aplicada a um programa que não termina, o resultado é F. Por exemplo, 
h(“x := 0”) = V 
h(“while V faça x := 1”) = F.
Se for assumido que h é computável, então um programa H que computa 
a função h pode ser escrito de forma que:
H(“x := 0”) = V 
H(“while V faça x := 1”) = F.
A Figura 2 ilustra o funcionamento do programa H representado por uma 
máquina de Turing MP (máquina da parada). Essa máquina recebe uma entrada 
w qualquer e retorna Sim (verdadeiro), caso ela consiga parar após um número 
finito de passos, ou Não (falso), caso contrário.
Figura 2. Máquina de Turing hipotética, que determina se um dado programa (informado 
como entrada) para ou não para.
Fonte: Adaptada de Tutorials Point (c2020).
Computabilidade10
Logo, é possível definir um programa D como segue:
D = “se H(D) então 
 enquanto V faça 
 x := 1 
 senão 
 x:= 0”.
Então, como o programa H aceita qualquer entrada, é possível passar 
para ele uma instância de si próprio tendo o programa D como parâmetro, ou 
seja, H(H(D)). Nesse caso, se H(D) é V (verdadeiro), então D representa um 
programa que é equivalente a “enquanto V faça x := 1”, cuja execução 
não termina; portanto, H(D) é falso. Por outro lado, se H(D) é F (falso), então 
D representa um programa que é equivalente a “x := 0” cuja execução 
termina; portanto, H(D) é verdadeiro. Dessa forma, uma inconsistência é 
obtida. Consequentemente, pode-se afirmar que o programa H não existe, 
o que, por sua vez, leva à conclusão de que a função h não é computável 
(HEHNER, 2018).
3 Classes de computabilidade
Conforme apresentado anteriormente, cientistas da computação geralmente 
consideram problemas solucionáveis por algoritmos de tempo polinomial 
como “tratáveis”, o que, de maneira informal, traz o signifi cado de “fácil 
de lidar”. Um algoritmo é dito de tempo polinomial se o seu tempo de 
execução no pior caso é limitado por um polinômio cujo grau é da ordem 
das instâncias do problema. Mais formalmente, um algoritmo é polinomial 
se existe um número i para todas as instâncias tal que a complexidade de 
tempo do algoritmo é O(ni), onde n corresponde ao tamanho da instância 
(FEOFILOFF, 2020). Nesse sentido, se existir um algoritmo de tempo 
polinomial para um dado problema, esse problema é dito como pertencente 
à classe P. 
11Computabilidade
Ainda que, para uma entrada de tamanho n = 10, um algoritmo demande um tempo 10100 
(a quantidade 10100 é conhecida como um googol, que deu origem ao nome “Google”), 
um problema que requer um tempo Θ(n100) é considerado como tratável. No entanto, na 
prática, poucos são os algoritmos dessa ordem de complexidade. Em geral, os problemas 
da classe P exigem muito menos tempo. Além disso, uma vez que um primeiro algoritmo 
de tempo polinomial é encontrado para um problema, normalmente novos algoritmos 
ainda mais eficientes são propostos na sequência (CORMEN, 2013). 
Há problemas, porém, verificáveis em tempo polinomial, mas para os 
quais ainda não foram encontrados algoritmos polinomiais que os resolvam. 
Problemas desse tipo são considerados como pertencentes à classe NP. Para 
resolver uma instância de um problema desse tipo, o melhor que se pode fazer 
é testar todos os candidatos à solução da instância. Outra característica desses 
problemas é a verificabilidade de suas soluções. Supondo que uma solução seja 
proposta para um dado problema, deseja-se verificar se a solução é correta ou 
não. Nesse sentido, outra característica de problemas da classe NP é que, para 
todos eles, é possível realizar a verificação de uma solução proposta em tempo 
polinomial. Uma solução apresentada para um problema NP é chamada de 
certificado. Além disso, para que um problema seja considerado NP, o tempo 
para se verificar um certificado deve ser polinomial e da mesma ordem que o 
tamanho da entrada do problema e do próprio certificado.
É importante nunca confundir problemas da classe NP com problemas não polino-
miais. Um problemas é dito NP se é verificável em tempo polinomial, mas ainda não 
foi encontrado um algoritmo que o resolva em tempo polinomial. Por outro lado, 
problemas não polinomiais não são problemas para os quais não conhecemos um 
algoritmo polinomial hoje, mas de problemas que nunca terão um algoritmo polinomial; 
ou seja, são problemas intratáveis (FEOFILOFF, 2020). 
Computabilidade12
Naturalmente, se um problema pode ser resolvido em tempo polinomial, 
então um certificado para esse problema também pode ser verificado em 
tempo polinomial. Em outras palavras, todo problema pertencente à classe 
P automaticamente pertence à classe NP. O inverso, no entanto, constitui 
uma questão em aberto há muitos anos. Cabe ressaltar a importância de 
não confundir problemas da classe NP com problemas não polinomiais. 
De fato, até os dias atuais, não foi encontrado um único problema NP 
provado que não esteja em P; ou seja, não foi identificado um problema 
que pode ser verificado em tempo polinomial, mas para o qual não exista 
um algoritmo polinomial que o resolva. Logo, a pergunta que padece de 
uma resposta formal é: Todo problema cuja soluçãopode ser verificada em 
tempo polinomial pode também ser resolvido por um algoritmo polinomial? 
(KLEINBERG; TARDOS, 2006).
Alguns exemplos clássicos de problemas da classe NP são os seguintes 
(ARORA; BARAK, 2007).
  Problema do caixeiro viajante: dado um número n de cidades 
(nós de um grafo), as distâncias di,j entre cada cidade (pesos das 
arestas) e um número k qualquer, decidir se é possível construir 
um circuito fechado em que um viajante visite todas as cidades 
exatamente uma única vez e cujo comprimento total corresponda 
a, no máximo, o valor de k. O certificado para esse problema é 
uma sequência de nós que compõe o circuito e pode ser verificado 
em tempo polinomial.
  Problema de programação linear: dada uma lista de m desigualdades 
lineares com coeficientes racionais sobre n variáveis u1, …, un (uma desi-
gualdade linear é da forma a1u1 + a2u2 + … + anun ≤ b para algum conjunto 
de coeficientes a1, …, an, b), decidir se existe uma atribuição de números 
racionais para as variáveis u1, …, un que satisfaça todas as desigualdades. O 
certificado para esse problema são os valores a serem atribuídos às variáveis.
  Soma de subconjunto: dados números naturais p1, …, pn e c, decidir 
se existe um subconjunto K de {1, …, n} tal que a soma Σ (pk : k Є K) 
seja igual a c.
13Computabilidade
Ainda existe outra classe de problemas que são considerados os mais 
difíceis da classe NP. Eles são conhecidos como problemas NP-completos. 
Informalmente, um problema é NP-completo se ele atende duas condições: 
(1) se está em NP e (2) se existir um algoritmo de tempo polinomial para o 
problema, então vai existir uma maneira de converter todos os problemas 
da classe NP nesse problema de maneira a resolvê-los em tempo polino-
mial. Logo, se existir um algoritmo de tempo polinomial para qualquer 
problema NP-completo (ou seja, se houver algum problema NP-completo 
em P), pode-se afirmar que P = NP. Como os problemas NP-completos 
são os mais difíceis da classe NP, se houver algum problema em NP que 
não é possível de ser resolvido em tempo polinomial, então nenhum dos 
problemas NP-completos é. 
Nesse contexto, outra classe de problemas é conhecida como NP-difícil. 
Um problema é dito NP-difícil se ele satisfizer a segunda condição de NP-
-completude, mas pode ou não estar em NP. O Quadro 2, a seguir, apresenta, 
de maneira sintética, uma descrição das classes de computabilidade nas quais 
os problemas podem ser agrupados, e a Figura 3 ilustra como essas diferentes 
classes estão relacionadas como conjuntos de problemas. 
Fonte: Adaptado de Cormen et al. (2009).
Classe Descrição
P Problema resolvível em tempo polinomial, com ordem corres-
pondente ao tamanho da entrada.
NP Problema para o qual não se conhece um algoritmo polino-
mial, mas que é verificável em tempo polinomial; isto é, dado 
um certificado, é possível verificar em tempo polinomial que o 
certificado é uma solução para ele.
NP-difícil Problema tal que, se existir um algoritmo polinomial que o 
resolva, será possível converter todos os problemas NP nele 
próprio, de modo a tornar possível que todo problema NP seja 
resolvido em tempo polinomial.
NP-completo Problema que é tanto NP-difícil quanto NP.
Quadro 2. Classes de computabilidade
Computabilidade14
Figura 3. Diagrama das classes de computabilidade supondo P contido 
em NP e P diferente de NP.
Fonte: Adaptada de Yun (2019).
Neste capítulo, o conceito de computabilidade foi amplamente explorado, 
apresentando uma visão clara de como os problemas são categorizados sob a 
óptica de sua tratabilidade. Ficou evidente que certos problemas não podem 
ser resolvidos por meio de um algoritmo com número finito de passos. Vários 
modelos computacionais e matemáticos disponíveis na literatura formalizam a 
inviabilidade computacional dessa classe de problemas. Entre esses modelos, 
a máquina de Turing foi destacada pela simplicidade e clareza na maneira de 
abordar o conceito de computabilidade. Esse mesmo conceito foi adicional-
mente abordado dentro das diferentes classes de problemas existentes. 
ARORA, S.; BARAK, B. Computational complexity: a modern approach. Princeton: Prin-
ceton University, 2007.
CORMEN, T. H. Algorithms unlocked. Cambridge: MIT Press, 2013.
CORMEN, T. H. et al. Introduction to algorithms. 3rd ed. Cambridge: MIT Press, 2009.
15Computabilidade
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computa-
bilidade. 3. ed. Porto Alegre: Bookman, 2011. 5 v.
FEOFILOFF, P. Complexidade: problemas NP-completos. 2020. Disponível em: https://
www.ime.usp.br/~pf/analise_de_algoritmos/aulas/Npcompleto.html#polynomial-
-algorithm. Acesso em: 27 ago. 2020.
GAREY, M. R.; JOHNSON, D. S. Computers and intractability: a guide to the theory of 
NP-Completeness. New York: Bell Telephone Laboratories, 1979.
HANSEN, E. Introduction to formal languages and automata. 2017. Disponível em: http://
web.cse.msstate.edu/~hansen/classes/3813spring05/slides/20Rice.pdf. Acesso em: 
27 ago. 2020.
HEHNER, E. C. R. Problems with the halting problem. 2018. Disponível em: https://www.
cs.toronto.edu/~hehner/PHP.pdf. Acesso em: 27 ago. 2020.
HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J. Introduction to automata theory, languages, 
and computation. 3rd ed. Boston: Pearson Education, 2007.
IMMERMAN, N. Computability and complexity. 2015. Disponível em: https://plato.stanford.
edu/entries/computability/#WhaComPriIntHis. Acesso em: 27 ago. 2020.
KLEINBERG, J.; TARDOS, E. Algorithm design. Boston: Pearson Education, 2006.
LECHENCO, G. A general introduction to turing machine. c2020. Disponível em: https://
iq.opengenus.org/general-introduction-to-turing-machine/. Acesso em: 29 jul. 2020.
SEN, S.; KUMAR, A. Design and analysis of algorithms: a contemporary perspective. 
Cambridge: Cambridge University Press, 2019.
TUTORIALS POINT. Turing Machine Halting Problem. c2020. Disponível em: https://
www.tutorialspoint.com/automata_theory/turing_machine_halting_problem.htm. 
Acesso em: 27 ago. 2020.
YUN, P. P, NP, NP-Hard, and NP-Complete problems. 2019. Disponível em: https://medium.
com/@p.yun1994/p-np-np-hard-and-np-complete-problems-fe679bd1cf9c. Acesso 
em: 27 ago. 2020.
Leitura recomendada 
PRINCETON UNVERSITY. What can and what cannot be computed? 2019. Disponível 
em: https://assets.press.princeton.edu/chapters/i11348.pdf. Acesso em: 27 ago. 2020.
Computabilidade16
Os links para sites da web fornecidos neste capítulo foram todos testados, e seu fun-
cionamento foi comprovado no momento da publicação do material. No entanto, a 
rede é extremamente dinâmica; suas páginas estão constantemente mudando de 
local e conteúdo. Assim, os editores declaram não ter qualquer responsabilidade 
sobre qualidade, precisão ou integralidade das informações referidas em tais links.
17Computabilidade