Please enable JavaScript.
Coggle requires JavaScript to display documents.
Problemas: P, NP e NP-Complete - Coggle Diagram
Problemas: P, NP e NP-Complete
Quando estudada a complexidade computacional de problemas, uma das primeiras abordagens tomadas é identificar se este problema pode ser resolvido em tempo polinomial por algum algoritmo.
Definições
Resolução em tempo polinomial: classificados assim aqueles algoritmos que, em seu pior caso, possuem tempo de eficiência classificado na faixa de big O(p(n))
-
-
Problemas de decisão: aqueles problemas nos quais os algoritmos de resolução devolvem uma resposta de sim ou não como resultado.
-
Problemas indecidíveis: problemas que não podem (ou pelo menos não em tempo hábil) serem resolvidos por algoritmos de decisão.
Algoritmos não deterministicos: são aqueles que, para serem executados, possuem dois estágios:
Parte não deterministica: uma string S é gerada arbitrariamente como uma possível solução para uma determinada instância I de um problema.
Parte deterministica: o algorítmo pega ambas as entradas I e S e, caso S seja de fato uma solução para a instância I, o algoritmo retorna true, caso contrário retorna false
Problemas polinomialmente redutíveis: um problema D1 é classificado como polinomialmente redutível a um problema D2 se existe uma função que transforma todas as instâncias de D1 em instâncias de D2 de modo que:
essa função mapeie todas as instâncias que retornam sim de D1 em instâncias de D2 que também retornem sim
-
Problemas de classe P (polinomial): são aqueles problemas de decisão que podem ser resolvidos por algoritmos deterministicos em tempo polinomial.
Problemas de classe NP (polinomial não-deterministico: são aqueles problemas de decisão que podem ser resolvidos por algoritmos não deterministicos em tempo polinomial
-
Ainda é uma questão da Ciência da Computação de a classe de algoritmos P incluem todos os algotitmos de classe NP, ou seja, se P é de fato um conjunto próprio de NP, ou se ambos os conjuntos são iguais.
Problemas de classe NP-Complete (polinomial não-deterministico completos): um problema de decisão D é classificado assim quando ele pertence a classe NP e quando todo problema de NP pode ser polinomialmente redutível a D.