Problemas Intrataveis

Problemas Intratáveis

Problemas intratáveis
Resumo
O resumo deve constituir-se num texto redigido de forma cursiva (sem parágrafos e com no mínimo 100 e no máximo 150 palavras), conciso e objetivo, respeitando a estrutura do original e reproduzindo apenas as informações mais significativas, como: objetivos, técnicas de abordagem, descobertas, valores numéricos e conclusões. Limita-se a um parágrafo, devendo incluir palavras representativas do assunto (palavras-chave). Deve-se evitar, no resumo: abreviaturas, símbolos, fórmulas, diagramas e notas de rodapé que não sejam absolutamente necessários à sua compreensão, bem como comentários, críticas e julgamento pessoal; palavras e/ou expressões supérfluas, tais como “o presente trabalho trata de...” ou “o autor do trabalho descreve...”, devem também ser evitadas. Estilo:
Palavras-Chave: Lista de palavras-chave, separadas por vírgulas. Estilo:

1. Introdução
A teoria da complexidade computacional é um ramo da teoria da computação em ciência da computação teórica e matemática que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si. Neste contexto, um problema computacional é entendido como uma tarefa que é, em princípio, passível de ser resolvida por um computador (o que basicamente significa que o problema pode ser descrito por um conjunto de instruções matemáticas). Informalmente, um problema computacional consiste de instâncias do problema e soluções para essas instâncias do problema.

2. Problemas intratáveis - definição
Problemas que podem ser resolvidos na teoria (por exemplo, dado um tempo infinito), mas que na prática levam muito tempo para as suas soluções sejam úteis, são conhecidos como problemas intratáveis. Na teoria da complexidade, os problemas que não apresentam soluções em tempo polinomial são considerados intratáveis por menores que sejam suas entradas. Na verdade, a tese de