A MáquinaExistem alguns problemas que são mais "fáceis" para um computador resolver que outros. Mas o que significa ser "fácil" pra um computador? Será o tempo que ele leva pra realizar uma tarefa? A quantidade de eletricidade que ele gasta? O tanto de memória necessária durante a execução?
E mais: existem "ene" tipos de computador diferentes. CPUs diferentes. PCs, MACs, tamagoshi, arquiteturas RISC, supercomputadores com centenas de cpus, Playstastion... Como definir a dificuldade de uma tarefa de forma independente do hardware que você tem?
A resposta é usar uma abstração chamada
Máquina de Turing. Ela criada pelo boiola Alan Turing nos anos 50, é mais ou menos assim: um computador imaginário feito de uma caixa que executa tudo (a cpu) uma fita de papel quadriculado cujo tamanho não importa qual é, mas é grande (ou memória) e um cabeçote de leitura e escrita, que fica posicionado em cima da fita. De acordo com o programa da máquina, ela a cada passo lê o que tem abaixo do cabeçote e ou escreve algo nele, ou chega a fita de papel pra direita ou pra esquerda.
Um troço desses é totalmente ridículo, mas serve de modelo matemático de toda computação capaz de ser efetuada por qualquer tipo de computador. Pra você entender a utilidade disso, pense da seguinte forma: Você quer viajar e quer saber quanto combustível vai gastar. Uma revista poderia publicar um mapa do Brasil com uma tabela do gasto de combustível entre cada cidade, e para cada tipo de motor carro. Seria uma lista enooorme. Ao invés disso, publica com a distância em quilômetros. Cada dono de carro sabe quanto gasta por quilômetro e faz as contas.
Então é isso: Os cientistas em computação publicam teoremas mostrando quantos passos uma máquina abstrata como a de Turing leva pra realizar cada tarefa, e cada dono de computador avalia aquilo pra máquina dele. (sim, eu estou supersimplificando, mas o princípio é esse)
O "tempo" então se "mede" em quantidade de passos e o espaço em memória em termos de quantidade de quadradinhos de papel usados.
Vamos dar um exemplo besta: colocar uma lista de nomes em ordem alfabética. Tem vários métodos pra fazer isso. Existe um muito simples que qualquer um aprendendo a programar computador pode fazer, que é o tal do
método da bolha. Quanto tempo ele leva? Se você tem 2 nomes pra ordenar, um número de passos lá... proporcional a 4. Se você tem 3 nomes um número proporcional a 9. Se você tem 1000, um número proporcional a 1.000.000. Enfim, você já viu falar em elevar um número ao quadrado, né?
Existem métodos melhores que o da bolha, mas não vou falar deles aqui. É só pra você entender que ele é do tipo n ao quadrado. Existem problemas que exigem um número de passos menor, outros maior.
Então... E tem um monte de problemas interessantes que todo mundo está interessado em resolver usando computador, mas que... hmm... Demorariam demais. Um desses, que vou detalhar agora, é o
problema do caixeiro viajante.
O VendedorUm vendedor precisa visitar um certo número de cidades pra sair oferecendo seus produtos. Ele tem um computador. Ele quer digitar no computador os nomes das cidades e uma tabelinha com as distâncias entre elas. Beleza. E quer agora que a máquina calcule a ordem que ele pode visitar as cidade de forma a percorrer a menor distância possível. Epa!
Se forem só umas 3 ou 4 cidades vá lá. Mas se o número for crescendo, não tem computador no mundo que dê jeito. Nem se juntarem todos os computadores do mundo, e desse pra cada um uma parte do problema. Não tem como. Ainda assim levaria milhões, bilhões de anos, dependendo do número de cidades. Ou mesmo milhares de vezes a idade do universo...
Isso porque não há um método conhecido que dê a resposta exata em um número decente de passos. Só existem os que levam um número exponencial de passos, ou que não dão sempre a resposta exata (mas algo aproximado) ou sei lá.
A quase um século se busca esse tipo de método, sem sucesso.
E se você está pensando "os vendedores viajantes que se danem", calma lá!
Os caras perceberam que existem esses problemas pra todo lado... Tráfego de dados na Internet. Alocação de encomendas no caminhão dos correios. Escalonamento de navios no porto. Uma porção de joguinhos, como Campo Minado, Sudoku. Inteligência Artificial.
Todos são problemas chamados de
intratáveis. Muitos deles tem relação direta com custos da indústria e aproveitamento de matérias primas e tempo e mesmo combustível. Um método decente de achar soluções boas para eles poderia diminuir custos (e muito), aquecer a economia, diminuir a poluição, e muitos outros benefícios. Na verdade isso é só a ponta de um iceberg. Métodos assim trariam um mega-benefício de forma que não vou explicar agora, mas dotaria a humanidade de poderes incríveis.
Uma boa notícia: Achar um método pra um dos problemas significa achar pra todos. Achar um método pra o problema do caixeiro viajante é o Santo Graal da Ciência da Computação. Há décadas que está todo mundo pensando nisso.
Mas como ninguém achou até agora... estamos achando que deva ser impossível.
Bem, é isso. Você já entendeu o que é o problema "P versus NP". Só falta explicar o que é esse nome.
As SiglasP vem de "Polinomial". É uma forma de caracterizar os algoritmos (que eu chamei de métodos neste texto) "fáceis": eles levariam um número de passos proporcional a um polinômio.
NP vem "Polinomial em Máquina de Turing Não-determinística". Não vou explicar o que é Não-determinística agora. Ao invés disso, deixa eu caracterizar o conjunto NP de outra forma:
Achar uma solução pro problema do caixeiro viajante pode ser difícil, mas... se você tiver achado uma e disser "eu tenho" o que você faz? Posta a solução num fórum de céticos. Lista lá "ele vai primeiro na cidade 1, depois na 17 ...". Eles vão conferir se a solução dá certo. E vão ter que te engolir.
Enfim: problemas NP são aqueles que, se você tem uma solução, mostre! Se ela é correta, isso pode ser verificado em tempo polinomial.
Perceba um detalhe que nem todo mundo se toca: Todo problema em P está dentro de NP também: Pra verificar é só rodar o algoritmo de novo. Olha a figurinha:
O PrêmioExiste um prêmio de um milhão de dólares pra quem responder a essa pergunta "existe um algoritmo polinomial pra resolver problemas NP-completos (como caixeiro ou equivalentes)? Se sim, mostre. Se não, mostre porquê."
Mas convenhamos, um problema dessa importância e impacto nem precisava desse prêmio mixuruca pra deixar todo mundo interessado.
Tópico: P versus NP - o tópico definitivo! (Lida 3246 vezes)