temos escrito sobre algoritmos eficientes para resolver problemas complexos, como o caminho mais curto, o grafo de Euler, a árvore de calibração mínima, etc. Eram histórias de sucesso de criadores de algoritmos. Neste post, histórias de falha da ciência da computação são discutidas.todos os problemas computacionais podem ser resolvidos por um computador? Existem problemas computacionais que não podem ser resolvidos por algoritmos mesmo com tempo ilimitado. Por exemplo, Turing parou o problema (dado um programa e uma entrada, se o programa irá parar quando executado com essa entrada, ou será executado para sempre). Alan Turing provou que o algoritmo geral para resolver o problema da parada para todos os pares de entrada de programas possíveis não pode existir. Uma parte chave da prova é, a máquina de Turing foi usada como uma definição matemática de um computador e programa (problema de parada fonte).o Status de problemas completos de NP é outra história de falha, problemas completos de NP são problemas cujo status é Desconhecido. No polynomial time algorithm has yet been discovered for any NP complete problem, nor has anybody yet been able to prove that no polynomial-time algorithm exist for any of them. A parte interessante é, se qualquer um dos problemas NP completos pode ser resolvido em tempo polinomial, então todos eles podem ser resolvidos.
What are NP, P, NP-complete and NP-Hard problems?P é um conjunto de problemas que podem ser resolvidos por uma máquina de Turing determinística em tempo polinomial.
NP é um conjunto de problemas de decisão que podem ser resolvidos por uma máquina de Turing não-determinística em tempo polinomial. P é um subconjunto de NP (qualquer problema que pode ser resolvido por máquina determinística em tempo polinomial também pode ser resolvido por máquina não-determinística em tempo polinomial).informalmente, NP é um conjunto de problemas de decisão que podem ser resolvidos por um tempo polinomial através de um “algoritmo de sorte”, um algoritmo mágico que sempre faz um palpite certo entre o conjunto dado de escolhas (fonte Ref 1).
NP-problemas completos são os problemas mais difíceis no conjunto NP. Um problema de decisão L é NP-completo se:
1) L está em NP (qualquer solução dada para problemas NP-completo pode ser verificada rapidamente, mas não há uma solução conhecida eficiente).
2) Todo problema em NP é redutível a L em tempo polinomial (redução é definida abaixo).
um problema é NP-difícil se ele segue a propriedade 2 mencionada acima, não precisa seguir a propriedade 1. Portanto, o conjunto NP-completo é também um subconjunto do conjunto NP-rígido.
decisão vs problemas de otimização
NP-completude aplica-se ao reino dos problemas de decisão. Foi configurado desta forma porque é mais fácil comparar a dificuldade dos problemas de decisão do que a dos problemas de otimização. Na realidade, porém, ser capaz de resolver um problema de decisão em tempo polinomial muitas vezes nos permitirá resolver o problema de otimização correspondente em tempo polinomial (usando um número polinomial de chamadas para o problema de decisão). Assim, discutir a dificuldade dos problemas de decisão é muitas vezes equivalente a discutir a dificuldade dos problemas de otimização. (Fonte Ref 2).
Por exemplo, considere o problema da cobertura de vértices (dado um grafo, descubra o conjunto de vértices de tamanho mínimo que cobre todas as arestas). É um problema de otimização. O problema de decisão correspondente é, dado o grafo G E k não direcionado, existe uma cobertura de vértices do tamanho k?o que é a redução?
Let L1 and L2 be two decision problems. Suponha que o algoritmo A2 resolve o L2. Isto é, se y é uma entrada para L2 então algoritmo A2 responderá Sim ou não dependendo se y pertence a L2 ou não.
A idéia é encontrar uma transformação de L1 para L2, de modo que o algoritmo A2 pode ser parte de um algoritmo A1 para resolver L1.a redução da aprendizagem em geral é muito importante. Por exemplo, se tivermos funções de biblioteca para resolver um certo problema e se pudermos reduzir um novo problema a um dos problemas resolvidos, pouparemos muito tempo. Considere o exemplo de um problema onde temos que encontrar o caminho mínimo do produto em um dado grafo direcionado onde o produto do caminho é a multiplicação de pesos das arestas ao longo do caminho. Se tivermos código para o algoritmo de Dijkstra para encontrar o caminho mais curto, podemos fazer log de todos os pesos e usar o algoritmo de Dijkstra para encontrar o caminho mínimo do produto ao invés de escrever um código novo para este novo problema.como provar que um dado problema está completo?a partir da definição de NP-completo, parece impossível provar que um problema L é NP-completo. Por definição, requer que mostremos que todo problema em NP é em tempo polinomial redutível a L. felizmente, há uma maneira alternativa de prová-lo. A idéia é pegar um problema conhecido NP-completo e reduzi-lo a L. Se em tempo polinomial redução é possível, podemos provar que L é NP-Completo pela transitividade de redução (Se um problema NP-Completo é redutível a L em tempo polinomial, então todos os problemas são redutíveis a L em tempo polinomial).
Qual foi o primeiro problema provado como NP-completo?
Deve haver algum primeiro problema NP-completo provado por definição de problemas NP-completo. SAT (problema de satisfatibilidade booleana) é o primeiro problema NP-completo provado por Cook.
é sempre útil saber sobre NP-completude mesmo para engenheiros. Suponha que lhe é pedido para escrever um algoritmo eficiente para resolver um problema extremamente importante para a sua empresa. Depois de muito pensar, você só pode chegar a uma abordagem de tempo exponencial, o que é impraticável. Se você não sabe sobre NP-completude, você só pode dizer que eu não poderia vir com um algoritmo eficiente. Se você sabe sobre NP-completude e provar que o problema como NP-completo, você pode orgulhosamente dizer que a solução de tempo polinomial é improvável de existir. Se existe uma solução em tempo polinomial possível, então essa solução resolve um grande problema da ciência da computação que muitos cientistas vêm tentando há anos.em breve estaremos discutindo mais problemas NP-completos e sua prova de NP-completude.