Articles

GeeksforGeeks

by admin

pré-Requisito: NP-Completude

NP Problema:
problemas NP conjunto de problemas cujas soluções são difíceis de encontrar, mas fáceis de verificar, são resolvidos pela Não-Determinista da Máquina em tempo polinomial.

NP-problema difícil:
Um problema X é NP-difícil se há um problema NP-completo Y, tal que Y é redutível a X em tempo polinomial. Os problemas NP-difíceis são tão difíceis como os problemas NP-completos. NP-problema difícil não precisa estar na classe NP.

NP-problema completo:

um problema X é NP-completo se há um problema NP Y, tal que Y é redutível a X em tempo polinomial. Os problemas NP-completos são tão difíceis quanto os problemas NP. Um problema é NP-completo se ele é uma parte de ambos NP e NP-problema difícil. Uma máquina de Turing não-determinística pode resolver um problema NP-completo em tempo polinomial.

diferença entre NP-dura e NP-completa:

NP-hard NP-Completo
NP-Problemas difíceis(digamos X) pode ser resolvido se, e somente se, existe um problema NP-Completo(digamos, Y) que pode ser redutível em X em tempo polinomial. NP-problemas completos podem ser resolvidos por um algoritmo determinístico annon / Máquina de Turing em tempo polinomial.
para resolver este problema, não tem que estar em NP . para resolver este problema, deve ser tanto NP e NP-problemas difíceis.
Do not have to be a Decision problem. It is exclusively a Decision problem.
Example: Halting problem, Vertex cover problem, Circuit-satisfiability problem, etc. Example: Determine whether a graph has a Hamiltonian cycle, Determine whether a Boolean formula is satisfiable or not, etc.