NP-complete

NP-complète English +ness Adjective - en computing theory of a decision problem That is both NP (solvable in polynomial time by a non-deterministic Turing machine) and NP-hard (such that any (other) NP problem can be reduced to it in polynomial time). en 2001 Thomas H Cormen; Charles E Leiserson; Ronald L Rivest; Clifford Stein Introduction To Algorithms w:The MIT Press 2nd https://books.google.com.au/books?id=NLngYyWFl_YC&pg=PA968&dq=%22NP-complete%22&hl=en&sa=X&ved=0ahUKEwja-cWY0L3ZAhVqmuAKHTGlC8sQ6AEISzAH#v=onepage&q=%22NP-complete%22&f=false 968 Informally, a problem is in the class NPC—and we refer to it as being NP-complete—if it is in NP and is as "hard" as any problem in NP. We shall formally define what it means to be as hard as any problem in NP later in this chapter. In the meantime, we will state without proof that if any NP-complete problem can be solved in polynomial time, then every problem in NP has a polynomial-time algorithm. Most theoretical computer scientists believe that the NP-complete problems are intractable, since given the wide range of NP-complete problems that have been studied to date—without anyone having discovered a polynomial-time solution to any of them—it would be truly astounding if all of them could be solved in polynomial time. Yet, given the effort devoted thus far to proving NP-complete problems intractable—without a conclusive outcome—we cannot rule out the possibility that the NP-complete problems are in fact solvable in polynomial time. en 2002 Thomas A. Garrity All the Mathematics You Missed: But Need to Know for Graduate School w:Cambridge University Press https://books.google.com.au/books?id=s_l6VK1ZPtMC&pg=PA317&dq=%22NP-complete%22&hl=en&sa=X&ved=0ahUKEwja-cWY0L3ZAhVqmuAKHTGlC8sQ6AEI7AIwOQ#v=onepage&q=%22NP-complete%22&f=false 317 Every area of math seems to have its own NP complete problems. For example, the question of whether or not a graph contains a Hamiltonian circuit is a quintessential NP complete problem and, since it can be explained with little higher level math, is a popular choice in expository works. en 2003 A. Schrijver Combinatorial Optimization: Polyhedra and Efficiency, Volume A https://books.google.com.au/books?id=mqGeSQ6dJycC&pg=PA43&dq=%22NP-complete%22&hl=en&sa=X&ved=0ahUKEwja-cWY0L3ZAhVqmuAKHTGlC8sQ6AEIhAEwEQ#v=onepage&q=%22NP-complete%22&f=false 43 Springer A problem Π is said to be NP-complete if each problem in NP is reducible to Π. Hence(4.13)     if some NP-complete problem belongs to P, then P=NP. Derived terms en co-NP-complete Related terms en NP NP-C,NPC<t:the set of NP-complete problems> NP-completeness NP-hard NP-easy NP-equivalent Translations both NP and NP-hard Dutch: nl NP-volledig, nl NP-compleet Finnish: fi NP-täydellinen French: fr NP-complet Georgian: ka NP-სრული German: de NP-vollständig Portuguese: pt NP-completo m Further reading P versus NP problem