DAA - Classe P & NP
Na Ciência da Computação muitos problemas são resolvidos onde o objetivo é maximizar ou minimizar alguns valores, enquanto em outros problemas tentamos descobrir se há uma solução ou não. Portanto, os problemas podem ser categorizados da seguinte forma -
Problema de Otimização
Problemas de otimização são aqueles cujo objetivo é maximizar ou minimizar alguns valores. Por exemplo,
Encontrar o número mínimo de cores necessárias para colorir um determinado gráfico.
Encontrando o caminho mais curto entre dois vértices em um gráfico.
Problema de Decisão
Existem muitos problemas para os quais a resposta é Sim ou Não. Esses tipos de problemas são conhecidos como decision problems. Por exemplo,
Se um determinado gráfico pode ser colorido por apenas 4 cores.
Encontrar o ciclo hamiltoniano em um gráfico não é um problema de decisão, enquanto verificar um gráfico é hamiltoniano ou não é um problema de decisão.
O que é linguagem?
Todo problema de decisão pode ter apenas duas respostas, sim ou não. Portanto, um problema de decisão pode pertencer a um idioma se ele fornecer uma resposta 'sim' para uma entrada específica. Um idioma é a totalidade das entradas para as quais a resposta é sim. A maioria dos algoritmos discutidos nos capítulos anteriores sãopolynomial time algorithms.
Para tamanho de entrada n, se o pior caso de complexidade de tempo de um algoritmo for O(nk), Onde k é uma constante, o algoritmo é um algoritmo de tempo polinomial.
Algoritmos como Matrix Chain Multiplication, Single Source Shortest Path, All Pair Shortest Path, Minimum Spanning Tree, etc. são executados em tempo polinomial. No entanto, existem muitos problemas, como vendedor ambulante, coloração ótima do gráfico, ciclos hamiltonianos, encontrar o caminho mais longo em um gráfico e satisfazer uma fórmula booleana, para a qual nenhum algoritmo de tempo polinomial é conhecido. Esses problemas pertencem a uma classe interessante de problemas, chamada deNP-Complete problemas, cujo estado é desconhecido.
Neste contexto, podemos categorizar os problemas da seguinte forma -
Classe P
A classe P consiste naqueles problemas que podem ser resolvidos em tempo polinomial, ou seja, esses problemas podem ser resolvidos em tempo O(nk) na pior das hipóteses, onde k é constante.
Esses problemas são chamados tractable, enquanto outros são chamados intractable or superpolynomial.
Formalmente, um algoritmo é um algoritmo de tempo polinomial, se houver um polinômio p(n) de modo que o algoritmo possa resolver qualquer instância de tamanho n em um tempo O(p(n)).
Problema exigindo Ω(n50) tempo para resolver são essencialmente intratáveis para grandes n. Algoritmo de tempo polinomial mais conhecido executado no tempoO(nk) para um valor bastante baixo de k.
As vantagens em considerar a classe de algoritmos de tempo polinomial é que todos os deterministic single processor model of computation podem ser simulados um no outro com no máximo um polinômio slow-d
NP-Class
A classe NP consiste nos problemas verificáveis em tempo polinomial. NP é a classe de problemas de decisão para os quais é fácil verificar a exatidão de uma resposta reivindicada, com o auxílio de algumas informações extras. Portanto, não estamos pedindo uma maneira de encontrar uma solução, mas apenas para verificar se uma suposta solução é realmente correta.
Cada problema nesta classe pode ser resolvido em tempo exponencial usando pesquisa exaustiva.
P versus NP
Todo problema de decisão que pode ser resolvido por um algoritmo de tempo polinomial determinístico também pode ser resolvido por um algoritmo não determinístico de tempo polinomial.
Todos os problemas em P podem ser resolvidos com algoritmos de tempo polinomial, enquanto todos os problemas em NP - P são intratáveis.
Não se sabe se P = NP. No entanto, muitos problemas são conhecidos em NP com a propriedade de que se eles pertencem a P, então pode-se provar que P = NP.
E se P ≠ NP, há problemas em NP que não estão em P nem em NP-Completo.
O problema pertence a classe Pse for fácil encontrar uma solução para o problema. O problema pertence aNP, se for fácil verificar uma solução que pode ter sido muito tediosa de encontrar.