O problema P versus NP

Fernando Ferreira
Departamento de Matemática da FCUL

1 Abertura
Por volta de 300 a.C., Euclides descreveu um algoritmo de recorrência
para calcular o máximo divisor comum entre dois números inteiros
positivos. Ei-lo:
euclides(a, b)
1 se b = 0
2 então o resultado é a
3 caso contrário o resultado é euclides(b, a mod b)
Como exemplo do processo computacional descrito pelo algoritmo
euclides, consideremos a computação do máximo divisor comum
entre os números 30 e 21:
euclides(30,21) = euclides(21,9)
= euclides(9,3)
= euclides(3,0) = 3
O algoritmo euclides descreve uma sequência de passos computa-
cionais que, a partir das entradas a e b, produz um determinado
resultado: a saber, o máximo divisor comum entre a e b. Não des-
crevemos exaustivamente todos os passos computacionais que sub-
jazem à execução do algoritmo. Por exemplo, não descrevemos os
passos computacionais que permitem calcular a mod b, i.e., o resto da
divisão inteira de a por b. Supusemos que esta computação não é
problemática e que é por demais conhecida dos leitores — de facto,
conhecida desde os primeiros tempos de escola.
Palestra √proferida no dia 19 de Outubro de 2000, integrada no ciclo “2000
matemática radical” do Departamento de Matemática da Faculdade de Ciências
da Universidade de Lisboa.

1
 Cada ciclo do algoritmo euclides calcula um resto. Estes restos
vão diminuindo sucessivamente, uma vez que o resto duma divisão é
sempre inferior ao divisor. Assim, mais tarde ou mais cedo, o resto
anula-se, entrando o algoritmo na cláusula de escape 2 e terminando
com o resultado final. O facto de o resultado estar correcto, i.e.,
de ser realmente o máximo divisor comum (mdc) dos dois números
dados, advém da seguinte igualdade: mdc(a, b) = mdc(b, a mod b).
Se quisermos saber se um número inteiro a, com a > 1, é um
número composto (i.e., não primo), podemos procurar exaustiva-
mente por um divisor de a, desde 2 até à sua raiz quadrada:
exaustão(a)
1 k←2
2 enquanto k 2 6 a
3 se a mod k = 0
4 então o resultado é SIM
5 caso contrário k ← k + 1
6 o resultado é NÃO
O algoritmo exaustão é iterativo e, dado a, a iteração pode ocor-
√
rer um número de vezes da ordem de a − 1. O número de cic-
los de euclides é muito menor: dados a e b, euclides tem, no
máximo, 2(1 + log2 a) ciclos. A razão para este facto não é difı́cil de
explicar. Basta observar que a cada dois ciclos de euclides o resto
diminui para, pelo menos, metade. Com efeito, se a mod b já fosse,
quanto muito, metade de b então, num só ciclo, o resto já se teria
reduzido o suficiente. Caso contrário, o resto seguinte seria b mod r,
com r = a mod b > 2b . Logo, o resto seria b − r < 2b ·
Os dois algoritmos acima dizem respeito a números inteiros posi-
tivos. Do ponto de vista computacional, estes números são dados em
notação posicional binária, i.e., como sequências apropriadas de 0s e
1s. O comprimento |a| dum número inteiro positivo a é o número
de bits que entra na sua representação binária. Não é difı́cil ver que
esse número difere de log2 a por, no máximo, uma unidade. Se n
for o máximo dos comprimentos das entradas a e b, então o número
de ciclos computacionais por que passa a execução de euclides está
limitado pelo valor 2(n + 2): na gı́ria matemática, é O(n). Por sua
vez, em cada ciclo, euclides efectua uma divisão inteira. Ora, o algo-
ritmo usual da divisão inteira é quadrático, i.e., efectua-se em O(n2 )
passos, onde n é o máximo dos comprimentos do dividendo e do divi-

2
sor. Em suma, euclides trabalha em O(n3 ) passos. euclides é um
algoritmo em tempo cúbico e, portanto, em tempo polinomial. Por
outro lado, para uma entrada a, o algoritmo exaustão pode ter que
√
sofrer a − 1 iterações. Se n for o comprimento de a, estas iterações
n
corresponderiam a cerca de 2 2 tarefas (e, portanto, a pelo menos
tantos passos computacionais). exaustão não é um algoritmo que
trabalhe em tempo polinomial.
Um algoritmo como exaustão não é eficiente do ponto de vista
prático. Um computador que trabalhe ininterruptamente a 1GHz
durante um ano efectua cerca de 3, 2 × 1016 passos computacionais.
n
Por sua vez, para n = 128, 2 2 é, aproximadamente, 1, 8 × 1019 . Por
conseguinte, um computador a 1GHz demoraria cerca de 563 anos
n
a executar 264 passos computacionais. Para n = 256, 2 2 é cerca de
3, 4×1038 . O nosso sistema solar tem, aproximadamente, 6×109 anos.
Consequentemente, todo esse tempo está ainda muitı́ssimo longe de
chegar para executar 2128 passos a 1GHz!

2 O enunciado do problema
Seja Σ um alfabeto finito (i.e., um conjunto finito e não vazio) e seja
Σ∗ o conjunto de todas as sequências finitas de elementos de Σ (as
palavras de Σ). Um problema é um subconjunto de Σ∗ . Por exemplo,
o conjunto de todos as palavras do alfabeto {0, 1} que representam
— em notação posicional binária — um número composto forma um
problema: o problema composto. Outro exemplo é o problema
de saber se o máximo divisor comum entre dois números inteiros
positivos é 1. Podemos formular este problema no alfabeto {0, 1, #}
como sendo o conjunto constituı́do pelas palavras da forma x#y, onde
x e y são palavras do alfabeto {0, 1} que representam números cujo
máximo divisor comum é 1. Chamamos a este problema primos-
entre-si.
Um problema L num alfabeto Σ diz-se decidı́vel em tempo polino-
mial se existir um algoritmo que trabalhe em tempo polinomial e que
termine em SIM sempre que a entrada x estiver em L, e que termine
em NÃO caso contrário. A classe P é a classe dos problemas de-
cidı́veis em tempo polinomial. Não definimos matematicamente nem
a noção de algoritmo nem a noção de passo computacional. Por con-
seguinte, a caracterização que acabámos de descrever é meramente

3
indicativa. A definição matemática, rigorosa, da noção de algoritmo
apareceu nos anos trinta do século passado, fruto de investigações
em lógica matemática (por, entre outros, Jacques Herbrand, Kurt
Gödel, Alonzo Church, Emil Post, Stephen Kleene e Alan Turing).
A definição de algoritmo devida a Turing não toma muito espaço.
Fornecemo-la no anexo a este artigo, tornando assim completa e ri-
gorosa a formulação do problema P versus NP aqui apresentada.
Um problema L num alfabeto Σ diz-se decidı́vel não deterministica-
mente em tempo polinomial se houver uma relação binária R em Σ∗ ,
decidı́vel em tempo polinomial, e houver um polinómio p(X) ∈ N[X]
tal que, para todas as palavras x ∈ Σ∗ ,

x ∈ L ⇔ ∃y (|y| 6 p(|x|) & xRy), (∗)

onde |x| denota o comprimento da sequência (palavra) x. A classe

NP é a classe dos problemas decidı́veis em tempo polinomial não
determinista.
Enunciado do problema: Será que P = NP?
É claro que composto ∈ NP, pois um número inteiro positivo a é
composto se, e somente se,

∃b (|b| 6 |a| & 1 < b < a & a mod b = 0).

Neste exemplo, a relação binária pertinente (dita relação de veri-

ficação) é a relação aRb ⇔ 1 < b < a & a mod b = 0. Note o leitor
que se trata duma relação decidı́vel em tempo polinomial. Todo o
problema em P (e.g., o problema primos-entre-si) está em NP por
razões triviais: se L ∈ P então L ∈ NP através da relação de veri-
ficação xRy ⇔ y = y & x ∈ L e tomando para p(X) o polinómio de
valor constante 1. O problema P versus NP é o problema de saber se
NP ⊆ P.
Dizemos que um problema L está na classe EXP se puder ser de-
cidido por um algoritmo que trabalhe em tempo O(2p(n) ), para um
certo polinómio p(X) ∈ N[X]. Dado L ∈ NP como em (∗), uma busca
exaustiva mostra que L ∈ EXP:

4
 forçabruta(x)
1 y←
2 enquanto |y| 6 p(|x|)
3 se xRy
4 então o resultado é SIM
5 caso contrário y ← s(y)
6 o resultado é NÃO
Aqui,  denota a palavra vazia e s(y) denota a palavra que se segue à
palavra y na seguinte ordenação total de Σ∗ : supondo que os elemen-
tos de Σ estão previamente ordenados, diz-se que uma palavra x ∈ Σ∗
precede outra palavra y ∈ Σ∗ se o comprimento da primeira for infe-
rior ao comprimento da segunda ou se, tendo ambas o mesmo com-
primento, então x precede y lexicograficamente. Seja m, com m > 1,
o número de elementos do alfabeto Σ. O número de palavras de Σ∗
n+1
cujo comprimento não excede n é mm−1−1 , o que permite concluir
que forçabruta trabalha em tempo O(2r(n) ), para certo polinómio
r(X).
A um valor y que testemunhe a verdade do segundo membro de (∗)
chama-se um certificado sucinto da afirmação x ∈ L. Dado x ∈ L, é
uma tarefa fácil verificar se um dado candidato a certificado sucinto
é, ou não, genuı́no; a dificuldade está em encontrá-lo no meio de
um potencial número exponencial de candidatos! É precisamente
nesta procura que reside a dificuldade de decidir a generalidade dos
problemas de NP.
Não se deve confundir a questão P = NP com a questão P = EXP.
Esta última questão tem uma resposta pronta: a teoria da comple-
xidade computacional mostra facilmente que há problemas em EXP
que não estão em P (através de um argumento de diagonalização:
ver adiante). Há pouco, vimos que NP ⊆ EXP, mas não se sabe se
NP = EXP. Os especialistas acreditam que não.

3 Completude NP
Sejam L1 e L2 dois problemas nos alfabetos Σ1 e Σ2 , respectivamente.
Diz-se que L1 se p-reduz a L2 , e escreve-se L1 ≤p L2 , se existir uma
função f : Σ∗1 7→ Σ∗2 , computável em tempo polinomial, tal que x ∈
L1 ⇔ f (x) ∈ L2 , para todos os elementos x de Σ∗1 . Se L1 ≤p L2 e

5
L2 ∈ P, conclui-se imediatamente que L1 ∈ P. Com efeito, decide-
se se x ∈ L1 calculando primeiro f (x) e, em seguida, testando se
f (x) ∈ L2 .
Um problema L diz-se NP-completo se L ∈ NP e se todo o problema
em NP se p-reduz a L. Se os houver, os problemas NP-completos são
os mais difı́ceis de entre os problemas em NP. Observe o leitor que
se um problema NP-completo estiver em P, então P = NP.
Em 1971, Stephen Cook mostrou que existem problemas NP-comple-
tos. Eis um exemplo dum problema NP-completo.
Um grafo finito orientado G é um par (V, E), onde V é um conjunto
finito e E é um subconjunto de V × V . Devemos interpretar os
elementos de V como sendo os vértices do grafo e cada par (x, y),
tal que xEy, como sendo um arco que liga x a y neste sentido. Um
caminho Hamiltoniano em G é uma permutação x1 , x2 , . . . , xn de V
tal que, para todo 1 6 i < n, se tem xi Exi+1 . Por outras palavras,
um caminho Hamiltoniano é um caminho através dos arcos do grafo
que passa por cada um dos seus vértices uma, e uma única, vez. Por
exemplo, o grafo

tem um caminho Hamiltoniano, e.g. 1 → 2 → 4 → 3 → 5 → 6.

Chamamos hamilton ao problema de saber se um dado grafo tem,
ou não, um caminho Hamiltoniano. Este problema é NP-completo.
Alguns leitores sentir-se-ão incomodados com a informalidade do
exemplo. Qual é o alfabeto Σ que subjaz a hamilton? De que
subconjunto L de Σ∗ se trata exactamente? Este tipo de informali-
dade é muito usual em teoria da complexidade computacional (e, em
geral, em matemática). Em ciência, a formalização é q.b. Quando
se apresenta um problema deste modo informal, pressupõem-se que

6
as entradas do problema (neste caso, os grafos) estão representadas
de alguma forma natural num determinado alfabeto. Por exemplo,
um grafo orientado de n vértices pode representar-se através da sua
matriz de adjacência n × n, cuja entrada aij é 1 se houver um arco
de i para j, e é 0 no caso contrário. A matriz de adjacência do grafo
do exemplo acima é:
 
0 1 0 1 1 0
 0 0 0 1 0 0 
 
 1 0 0 0 1 0 
 
 0 0 1 0 0 0 
 
 0 0 0 0 0 1 
0 0 1 1 0 1
Uma matriz de 0s e 1s representa-se muito facilmente no alfabeto
{0, 1, #}, com o sinal # a desempenhar o papel de separador das
linhas da matriz. Claro que há outras maneiras de representar natu-
ralmente um grafo. Isso é indiferente no que concerne aos nossos
estudos, desde que as diferentes representações sejam funções com-
putáveis em tempo polinomial umas das outras. Por sua vez, os
caminhos Hamiltonianos também se representam naturalmente no
alfabeto {0, 1, #}. O caminho do exemplo pode representar-se por

1#11#1111#111#11111#111111.

Com esta representação, os caminhos Hamiltonianos

Pn dum grafo com
n vértices são sempre palavras de comprimento i=1 i +(n−1) 6 n2 .
Logo, x ∈ Hamilton se, e somente se,

∃y (|y| 6 |x|2 & “y é um caminho Hamiltoniano do grafo x”),

pois o comprimento da representação de um grafo majora o número

de vértices desse grafo. Tendo em conta que a relação binária “y é um
caminho Hamiltoniano do grafo x” é decidı́vel em tempo polinomial,
concluı́mos que hamilton ∈ NP. De facto, hamilton é um problema
NP-completo. Qual é a razão para isso?
Historicamente, o primeiro exemplo de problema NP-completo foi
o problema satisfação. Este problema consiste em decidir se uma
fórmula do cálculo proposicional é satisfazı́vel, isto é, se podemos
dar valores de verdade às suas variáveis proposicionais de modo a
que o valor da fórmula resulte verdadeiro. Stephen Cook mostrou

7
essencialmente o seguinte. Dado um problema em NP da forma
∃y (|y| 6 p(|x|) & xRy) e dada uma máquina de Turing M (vide
anexo) que decida a relação de verificação R em tempo polinomial,
há uma função computável em tempo polinomial que, dada a en-
trada x, computa uma fórmula proposicional Fx — a qual “descreve”
a computação de M quando são introduzidas as entradas x e y,
com (algumas) das variáveis proposicionais a representar a palavra
desconhecida y — tal que Fx é satisfazı́vel se, e somente se, para
um certo y com |y| 6 p(|x|), M decide afirmativamente que xRy.
Foi com esta receita universal que Cook mostrou que satisfação é
um problema NP-completo. Atendendo à transitividade da relação
de p-redutibilidade, qualquer problema de NP em relação ao qual
satisfação se p-reduza é um problema NP completo. Há, portanto,
um método prático para demonstrar que um determinado problema
de NP é NP-completo: basta mostrar que satisfação se p-reduz a
esse problema.
Mais geralmente, um problema de NP em relação ao qual um de-
terminado problema NP-completo se p-reduza, é NP-completo. É
o que acontece com hamilton e com centenas de outros proble-
mas que aparecem naturalmente em teoria dos grafos, combinatória,
programação matemática, problemas de tabelamento, etc. Alguns
destes problemas têm uma importância industrial tremenda. A exis-
tência de um algoritmo verdadeiramente eficiente que pudesse decidir
satisfação teria consequências revolucionárias na indústria. Em
contrapartida, como abordamos na próxima secção, destruiria a se-
gurança das transacções financeiras na internet e através de outras
vias electrónicas.

4 Criptografia
Entre os matemáticos, são bem conhecidas as opiniões puristas do
grande matemático inglês Godfrey Hardy (1877-1947). Na sua au-
tobiografia A Mathematician’s Apology (Cambridge University Press,
1992), escreveu: “Nunca fiz nada de ‘útil’. Nenhuma descoberta
minha fez, nem é provável que faça, directa ou indirectamente, para
o bem ou para ou mal, a mais pequena diferença para a aprazibili-
dade do mundo”. Ironicamente, a área da matemática a que Hardy se
dedicava — a teoria dos números — tem tido, desde os anos setenta,

8
importantı́ssimas aplicações à segurança das transacções comerciais
e, mais geralmente, à confidencialidade das transmissões secretas.
Um sistema criptográfico K é um par (cK , dK ), onde cK contém a
informação necessária para o emissor codificar mensagens (é a chave
de codificação) e dK contém a informação necessária para o receptor
ler mensagens codificadas (é a chave de descodificação). Nos sistemas
criptográficos clássicos, dK obtém-se facilmente a partir de cK . Para
usar estes sistemas é condição sine qua non haver uma comunicação
prévia e secreta entre emissor e receptor para concertar o par crip-
tográfico. Sistemas como estes chamam-se sistemas de chave privada.
Em 1978, Ronald Rivest, Adi Shamir e Leonard Adleman propuseram
o primeiro sistema de troca de mensagens de chave pública, hoje con-
hecido por RSA. Neste sistema, o receptor fabrica previamente o par
criptográfico (cK , dK ), torna pública a chave de codificação cK (em
particular, torna-a conhecida do emissor) e guarda para si a chave
dK , pelo que não há necessidade de uma comunicação secreta entre
emissor e receptor. A segurança deste sistema está na convicção de
que é computacionalmente impraticável deduzir dK a partir de cK . O
sistema RSA continua a ser um dos mais seguros conhecidos, sendo
o mais utilizado para codificar mensagens através da internet.
A segurança do sistema RSA baseia-se no facto de que é muito fácil
multiplicar números, enquanto que há a convicção de que é muito
difı́cil factorizá-los (correntemente, é impraticável factorizar regular-
mente números com 200 casas decimais). Se P = NP, então factorizar
seria fácil. Com efeito, o problema

Lf ac = {(k, a) : ∃d (1 < d < k & a mod d = 0)}

está em NP. Dado um inteiro a, com a > 1, o seu mais pequeno

divisor primo pode encontrar-se por meio duma pesquisa binária na
qual se consulta Lf ac cerca de log2 a vezes. Portanto, se Lf ac ∈ P
então poderı́amos encontrar o mais pequeno divisor de a em tempo
polinomial. Repetindo o processo, poderı́amos factorizar a em tempo
polinomial. Em suma,

P = NP ⇒ factorizar é fácil.

Tanto quanto se sabe, pode acontecer P 6= NP e, ainda assim, ser fácil

factorizar. Há mesmo quem encare seriamente esta possibilidade,

9
baseado na convicção de que ainda não se trabalhou suficientemente
no assunto.
Alguns problemas que advêm da teoria dos números têm um es-
tatuto muito interessante e curioso. Por exemplo, o problema com-
posto está em NP, mas é muito duvidoso que seja NP-completo.
Em 1975, Vaughan Pratt mostrou que o problema de decidir se um
dado número inteiro é, ou não, primo está em NP. Dito de outro
modo, os números primos têm certificados sucintos! Por conseguinte,
composto é um problema que está em NP e cujo problema com-
plementar (essencialmente o problema primo há pouco mencionado)
também está em NP. Pensa-se que os problemas complementares de
problemas NP-completos não estejam em NP pois, caso contrário, to-
dos os problemas em NP teriam os seus complementares também em
NP.
Um pouco surpreendentemente, em 1976, Gary Miller mostrou
que primo ∈ P, desde que se admita uma determinada conjectura
matemática: a Hipótese Generalizada de Riemann1 . Entre os espe-
cialistas de teoria dos números há a convicção de que esta hipótese
é verdadeira. Note-se, porém, o seguinte: ainda que primo ∈ P,
não se segue necessariamente que factorizar seja fácil, pois poderá
não haver nenhuma redução em tempo polinomial do problema de
procura (search problem) factorização para o problema de decisão
primo. A inexistência de tal redução foi recentemente conjecturada
por Stephen Cook.

5 Súmula
No dia 24 de Maio de 2000, numa conferência no Collège de France em
Paris, o Clay Mathematics Institute de Cambridge (Massachusetts)
pôs a concurso sete problemas de matemática. O prémio atribuı́do
à solução de cada um destes “Millennium Prize Problems” é de um
milhão de dólares americanos. O primeiro problema da lista é o pro-
blema P versus NP. De algum modo, este problema é diferente dos
restantes, na medida em que pertence a uma área cientı́fica relativa-
mente recente, sem o corpo de conhecimentos e grau de sofisticação
matemática de outras áreas mais nobres e antigas da matemática.
1
A Hipótese de Riemann aparece referida no artigo de Nuno Costa Pereira, no
presente volume

10
 A maior parte dos especialistas acredita que P 6= NP, ainda que
tenham havido — e, certamente, continuarão a haver — tentativas
sérias de decidir em tempo polinomial determinados problemas NP-
completos. O método par excellence de separar classes de complexi-
dade computacional é o método da diagonalização. Este método per-
passa a lógica matemática e teve a sua origem há mais de um século
num célebre argumento de Georg Cantor no âmbito da teoria dos con-
juntos. Infelizmente, tem sido impotente para separar as classes P e
NP. Métodos alternativos, como argumentos combinatoriais com-
plicados na teoria dos circuitos Booleanos, parecem estar longe de
conseguir abordar a plenitude do problema. Sendo verdade que nos
últimos trinta anos se aprendeu muito acerca da natureza do pro-
blema P versus NP, também não deixa de ser verdade que ninguém
hoje sabe realmente como abordar o problema. Não obstante, não se
pode excluir que alguém, com um golpe de asa, consiga separar P de
NP através dum argumento relativamente elementar.

Q: P = NP?
R: Não.
Q: Factorizar é difı́cil?
R: A respeito desta questão, sou agnóstico.
Q: Quando será resolvido o problema P versus NP?
R: Circa 2015.
Q: Quem o resolverá?
R: Talvez o meu caro leitor!

6 Anexo sobre máquinas de Turing

Dado um alfabeto Σ, uma máquina de Turing é, informalmente,
uma sequência finita de instruções que rege uma cabeça móvel de
leitura e escrita a qual, em cada momento, visiona uma célula duma
fita de trabalho. Esta fita é infinitamente prolongável em ambas as
direcções e está dividida em células contı́guas. Em cada célula está
inscrito um sı́mbolo de Σ ou, então, não está nada inscrito (neste
caso, também se diz que a célula está em branco, ou que nela está o
sı́mbolo especial b). Em cada momento da computação, a máquina de
Turing está num determinado estado q de entre um conjunto (finito),
previamente especificado, de estados Q. O que a máquina faz no

11
momento seguinte depende do estado em que está, do sı́mbolo que a
cabeça está a ler e daquilo que consta na lista de instruções (função
de transição).
Definição. Seja Σ um alfabeto e b ∈ / Σ. Uma máquina de Turing
(determinista) M no alfabeto Σ é um par (Q, Θ), onde Q é um con-
junto finito não vazio com três elementos especiais q0 , qs e qn , e onde
Θ é uma função de (Q\{qs , qn })×(Σ∪{b}) para Q×(Σ∪{b})×{−1, 1}.
Suponhamos que Θ(q, σ) = (q 0 , σ 0 , δ), que M está no estado q e
que a sua cabeça está sobre uma célula cujo sı́mbolo inscrito é σ.
No passo subsequente, M passa para o estado q 0 , substitui na célula
em questão o sı́mbolo σ por σ 0 e move a cabeça para a esquerda ou
para a direita conforme δ é −1 ou 1, respectivamente. As próximas
definições formalizam estas ideias.
Definição. Seja M uma máquina de Turing no alfabeto Σ. Uma
configuração C de M é um triplo (x, q, y) com x e y palavras de
Σ ∪ {b}, y 6=  (i.e., y não é a palavra vazia) e q ∈ Q.
Sendo y 6= , então y é da forma sw, com s ∈ Σ ∪ {b} e w ∈
(Σ ∪ {b})∗ . Dito de outro modo, y é a concatenação dum sı́mbolo de
Σ ∪ {b} com uma palavra (possivelmente vazia) de Σ ∪ {b}. Dizer que
a máquina M está na configuração (x, q, sw) significa dizer que M
está no estado q, que a sua cabeça está sobre uma célula cujo sı́mbolo
inscrito é s, que à esquerda dessa célula consta a palavra x e que à
sua direita consta a palavra w. Com esta interpretação, seguem-se
duas definições naturais:
Definição. Sejam C e C 0 configurações duma máquina de Turing
M . Diz-se que C →M C 0 se C = (x, q, sy), Θ(q, s) = (q 0 , s0 , h) e se se
der um dos seguintes casos:
1. h = 1, y 6=  e C 0 = (xs0 , q 0 , y).
2. h = 1, y =  e C 0 = (xs0 , q 0 , b).
3. h = −1, x é da forma x0 t, onde t ∈ Σ ∪ {b}, e C 0 = (x0 , q 0 , ts0 y).
4. h = −1, x =  e C 0 = (, q 0 , bs0 y).
Definição. A computação finita da máquina de Turing M com
entrada x ∈ Σ∗ \ {} é, quando existe, a única sequência finita
C0 , C1 , . . . , Ck de configurações tal que C0 = (, q0 , x), Ci →M Ci+1
para todos os i < k, e tal que o estado de Ck é qs ou qn .

12
 Observe-se que, dada uma entrada, pode não haver uma com-
putação finita, devido à circunstância de nunca se atingir um estado
de paragem qs ou qn (chamados estados de aceitação e de rejeição,
respectivamente).
Definição. Seja L um problema no alfabeto Σ. Diz-se que L é
decidı́vel em tempo polinomial se existir uma máquina de Turing M
no alfabeto Σ e se houver um polinómio p(X) ∈ N[X] tais que, para
todas as entradas x ∈ Σ∗ ,

1. há uma computação finita C0 , C1 , . . . , Ck com k 6 p(|x|),

2. se o estado de Ck é qs então x ∈ L,

3. se o estado de Ck é qn então x ∈
/ L.

7 Brevı́ssima nota bibliográfica

Uma concisa e excepcional exposição sobre o problema P versus NP
— que inclui um pouco da sua história e comentários sobre os seus
desenvolvimentos mais recentes — deve-se ao próprio Stephen Cook
no artigo de apresentação do problema para os “Millennium Prize
Problems”. Neste artigo, o leitor também pode encontrar referências
bibliográficas pertinentes. O artigo intitula-se “The P versus NP
Problem” e encontra-se disponı́vel no endereço URL:
[Link]
O livro “Algorithmics: the Spirit of Computing” de David Harel
(Addison-Wesley, 2a edição, 1992) é uma excelente introdução à al-
goritmia e à complexidade computacional para leitores com uma
formação universitária cientı́fica geral. Uma introdução mais tradi-
cional a estes assuntos — de facto, um excelente manual universitário
— é o (longo) texto “Introduction to Algorithmics” de Thomas Cor-
men, Charles Leiserson, Ronald Rivest e Clifford Stein (The MIT
Press, 2a edição, 2001).
Sobre o assunto da complexidade computacional propriamente dita,
recomendo o livro de Christos Papadimitriou intitulado, precisamente,
“Computational Complexity” (Addison-Wesley, 1994). A meu ver,
este livro tem a clarividência de colocar a lógica matemática como
firme peça central nestas coisas da ciência da computação. Trata-se

13
dum livro avançado, ao nı́vel dum quarto ano de uma licenciatura em
Informática ou Matemática. Em português, Jorge Orestes Cerdeira
tem umas notas na internet intituladas “Umas Coisitas de Grafos e
uma Introdução Informal à Complexidade Computacional”. O en-
dereço URL é:

[Link]
Com excepção desta última referência, todas as outras abordam,
com maior ou menor detalhe, questões criptográficas. Carlos Sarrico
tem um pequeno artigo em português intitulado “Os Números Primos
e o Sistema de Codificação R.S.A.” (Boletim da Sociedade Portuguesa
de Matemática no 33, 1995, pp. 81-89) que descreve e analisa o sis-
tema criptográfico RSA. Para um estudo mais sistemático, recomendo
“A Course in Number Theory and Cryptography” de Neal Koblitz (2a
edição, Graduate Texts in Mathematics 114, Springer-Verlag, 1994).
Finalmente, no apêndice do livro “Computers and Intractability: a
Guide to the Theory of NP-completeness” de Michael Garey e David
Johnson (W. H. Freeman and Co., 1979), o leitor pode encontrar uma
lista com cerca de três centenas de problemas NP-completos.

8 Agradecimentos
Gostaria de agradecer a Miguel Ramos pelo amável √ convite para
participar no ciclo de conferências “2000 matemática radical” e pelo
cuidado e interesse que, tanto ele como Jorge Nuno Silva, tiveram com
a edição deste artigo.
Isabel Oitavem e Jorge Orestes Cerdeira leram uma versão prelimi-
nar deste artigo, tendo sugerido algumas correcções e melhoramentos.
Agradeço-lhes o interesse e a disponibilidade manifestados. É claro
que a responsabilidade última pelo que aqui está escrito cabe apenas
a mim próprio.
Classificação AMS 2000: 03, 68
Fernando Ferreira
Departamento de Matemática, Faculdade de Ciências
Campo Grande, Edifı́cio C1, 3o piso, 1749-016 Lisboa
fjferreira@[Link]
[Link]

14