Page 45 - Telebrasil - Novembro/Dezembro 1986

0 l i m i a r d a c o m p u t a ç ã o '

Volta e meia, matemáticos compare­ caso n fosse igual a 20; 1 minuto se n fos­ se caracterizam por serem de fácil veri­

cem ao Informática da Sucesu (vide Re­ se 26; 1 hora quando n for 31; e nada me­ ficação (solução parcial), mas de difícil

vista Telebrasil M/J, pg. III) para falar nos que mil anos! quando n atingisse 56. solução global.

daquilo que mais gostam — qual o li­ A explosão combinatória facilmente le­ Existem, portanto, dois tipos de pro­

mite do computador para solucionar va os computadores a impossibilidades blemas: os que levam tempo polinomial

problemas. Nesta categoria, se situa a práticas — inferiu Karp. para serem resolvidos (P) e os NP (não

visita que Richard Karp, full professor Graças a Deus, disse ele, existem al­ polinomiais), que são de difícil solução,

da Caltech e de Berkeley (USA) e pes­ guns truques que podem simplificar as mas de fácil verificação e que às vezes

quisador da IBM, fez recentemente ao coisas, tal como o de se contentar com podem ser solucionados quando se efe­

Brasil. Sua especialidade: a Complexi­ soluções particulares, abandonando a tuam tentativas dirigidas na direção

dade Computacional. solução global — dentro de filosofia de correta, empregando uma espécie de

que "o pior inimigo do bom é o ótimo”. "sexto sentido”.

Explosão
Novamente, o conferencista partiu de Os problemas que apresentam solu­

um exemplo bem simples. Seria tomar ção computacional são aqueles cujo

Para ele, a Complexidade Compu­ duas listas — uma de rapazes e outra de tempo de resolução permanece compatí­

tacional se cliva segundo 3 vertentes: a moças — e com elas formar casais de vel com a potência de entrada, isto é,

dos problemas que teoricamente não modo que todos fiquem igualmente sa­ com tempos de resolução do tipo n, n2, n'.

possuem solução (estão Já para aqueles problemas

natimortos para efeito de que recaem em expressões

computação); os que a pos­ do tipo 2", 3n, n! sua resolu­

suem, mas não são possí­ ção levará tanto tempo

veis de solução prática (le­ que provavelmente será

vam demasiado tempo de inexeqüível na prática.

cálculo); e os que são exe- Para Karp, são proble­

qüíveis, na prática. mas de fácil verificação:

Numa apresentação um jogo de armar (uma vez

aparentemente singela, armado sabe-se que existe

mas de complexa concei- uma solução); a divisão de

tuação, Karp chamou a uma herança entre herdei­

atenção para as trê s ros; uma listagem de ca­

idéias-chave da Complexi­ sais amigos. São proble­

dade: os problemas NP mas de difícil solução:

completos (de difícil solu­ achar as combinações pos­

ção, mesmo no futuro); a síveis entre todas as peças

criptografia com chave pú­ de um jogo de armar; saber

blica (desde 75, uma re­ todas as divisões possíveis

volução no sigilo da infor­ de herança entre herdei­

mação codificada); e as ros; e todas as combina­

provas interativas. Em se­ ções de casais amigos.

guida, explicou estes con­ Então, qual a relação

ceitos. entre os problemas fáceis

Começou o palestrante de resolver (Polinomiais) e

sua exposição, com um os fáceis de verificar se

simples exemplo. Seja, dis­ possuem solução (NP)?

se ele, o problema de deter­ Os problemas NP re­

minar de todos os modos caem em geral em proble­

possíveis dividir uma he­ mas combinatórios com­

rança, constituída de mui­ plexos (vide box), mas

tos objetos, entre duas pes­ Cook provou, em 1971, que

soas. Este é um tipo de pro­ os problemas da classe NP

blema que leva à denominada explosão tisfeitos. Mas há algumas restrições: podem ser resolvidos de maneira efi­

combinatória, ou seja, é um problema João só quer casar com Maria; Cristina ciente se surgir um bom algoritmo para

que toma um tempo "exponencialmente aceita qualquer um, exceto André; Jo- uma de suas soluções. Um problema é

longo” para ser resolvido. Mais precisa­ safá não quer Cristina; e assim por NT completo, disse Richard Karp,

mente, se não é o "tamanho” da descri­ diante. "quando qualquer problema no domínio

ção do problema, é preciso, no máximo, Este é um caso típico de problema de­ NP pode ser reduzido a este problema,

tempo proporcional a 2n para resolvê-lo. nominado "encaminhamento de uma em tempo polinomial”.

E o que isto significa? solução parcial” e que pode ser resolvido a Um problema que os matemáticos

— Caso se tivesse um computador ca­ verificando todos arranjos possíveis do têm procurado solucionar por séculos a

paz de testar 1 milhão de alternativas tipo nk. Caso se tivesse o mesmo compu­ fio e que ainda desafia a modernidade

por segundo, e o mesmo fosse confron­ tador do exemplo anterior com capaci­ (com ou sem computadores) é o proble­

tado com um problema do tipo 2n, ele le­ dade de 1 milhão de testes por segundo, ma da fatoração, ou seja, decompor um

varia 1 segundo para chegar à solução, quando n for igual a 100 ele levaria 30 número em seus divisores primos. Se­

segundos; e para n igual a 2000, apenas gundo o palestrante, ainda se ignora,

Telebrasil agradece a revisão de Marco Antomo seis minutos. Estes tipos de programas por exemplo, se achar os fatores primos

y asa no va, especialista do Centro Científico da
denominam-se NP (Não Polinomial) e de um número de 100 dígitos decimais é |