Glossário
Conjetura resultado matemático que se presume ser verdadeiro , embora tal não tenha sido ainda demonstrado ou refutado .
Grafo é uma representação abstrata de um conjunto de objetos ( por exemplo cidades ) e das relações existentes entre eles ( por exemplo duas cidades estarão relacionadas se existe uma estrada direta entre as duas cidades ).
Existem diversos problemas em que , intuitivamente , é difícil obter a solução sem nenhuma ajuda , mas uma vez que ela nos é dada , é relativamente fácil verificar se esta solução está correta ou não . Pode-se pensar na analogia com o problema muitas vezes evocado de procurar uma agulha num palheiro . Sem nenhuma informação , esta é uma tarefa quase impossível . No entanto , se alguém nos disser que sabe onde a agulha está e nos diz a localização dela , é muito fácil verificar se esta solução está correta ou não . Este tipo de problema é frequente em ciência . Por exemplo , dado um conjunto de dados experimentais acerca de um determinado fenómeno físico , é possível estabelecer uma teoria que explique este fenómeno ? Estabelecer a teoria é habitualmente uma tarefa difícil , mas é normalmente mais fácil testar se uma determinada teoria está de acordo com os dados experimentais .
No caso da Matemática , dada uma determinada conjetura ( resultado em aberto ), será que existe uma demonstração para esta conjetura ? Obter uma demonstração pode ser em geral uma tarefa quase impossível ( por exemplo , existem numerosas conjeturas em aberto há largas décadas que não se sabe se são verdadeiras ou não ), mas verificar a demonstração é uma tarefa ( relativamente ) bem mais fácil . Outro exemplo é o representado na Fig . 1 , onde um conjunto de cidades está ligado por estradas ( matematicamente este tipo de estrutura designa-se de grafo ).
Figura 1 . Exemplo de grafo .
Classe P classe de problemas cuja solução pode ser obtida em tempo razoável .
Classe NP classe de problemas cuja solução pode ser verificada em tempo razoável .
Existem técnicas que nos permitem saber de forma relativamente eficiente se é possível efetuar um trajeto pelas estradas passando por todas as estradas exatamente uma vez , mesmo no caso de haver milhões de cidades ( neste caso utilizando a ajuda de um computador . Por exemplo existe um trajeto deste tipo na Fig . 1 ). No entanto , o problema de determinar se existe um trajeto que passe por todas as cidades exatamente uma vez é em geral muito difícil , especialmente em mapas com um número significativo de cidades ( o caso com mil cidades não é , regra geral , resolúvel mesmo com recurso a supercomputadores ).
Em Matemática estas ideias podem ser formalizadas , originando a classe P dos problemas cuja solução pode ser obtida em tempo razoável ( como o caso do trajeto que passa por cada estrada exatamente uma vez ) e a classe NP dos problemas cuja solução , se nos for dada , pode ser verificada em tempo razoável , mesmo que esta solução seja ( ou não ) praticamente impossível de obter ( como é o caso do trajeto que passa por cada cidade exatamente uma
31