NP Complete

3 Key excerpts on "NP Complete"

• 

  eBook - ePub

  Automata and Computability

  A Programmer's Perspective

  • Ganesh Gopalakrishnan(Author)
  • 2019(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  16 NP-Completeness

  Chapter Gist: There are many important practical problems for which no polynomial time (P) algorithms are known. These problems can, so far, only be solved in nondeterministic polynomial time (NP), and currently this amounts to being intractable (exponential or worse). We define NP to be the class of polynomial time verifiable problems, and NP-Complete to be the hardest of all NP problems (§16.1). We present the role of NDTMs in formulating the theory of NP-Completeness in precise terms (§16.2). We take up the study of the Boolean satisfiability problem (SAT) given it has the distinction of being the first NP-Complete (NPC) problem identified (§16.3). We explain why SAT matters in practice, and also introduce a SAT-solver that can run within your own web browser (§16.8). We begin with the simpler 2-SATpolynomial time algorithm (§16.3.1). We describe a canonical problem called 3-SAT, and describe its role in showing new problems to be NP-Complete (§16.4). The idea of mapping reductions is central to this study, and we show that 3-SAT itself can be shown to be NP-Complete (§16.5). We show that the problem of finding k-cliques in a graph is NP-Hard by presenting a mapping reduction from 3-SAT to it (§16.6). We finish with some caveats and also a discussion of CoNP and allied complexity classes (§16.7).

  16.1  What Does NP-Complete Mean?

  In the 1960s, computer scientists started noticing that many problems defy polynomial time algorithms; all they could come up with were exponential (or worse) algorithms. Examples of these problems included everyday scheduling problems such as the Traveling Salesperson Problem (TSP), one version of which is the following. Suppose you are asked to start from Salt Lake City, UT, travel by road and visit all the 48 US state capitals of the contiguous USA exactly once and return to Salt Lake City in 18 days or less.1 What is the optimal route you would take?2 Is there a better algorithm than computing the cost of all 48! such tours and picking the one that finishes in 18 days or less? All algorithms so far have been intractable (exponential or worse;

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  An Elementary Approach to Design and Analysis of Algorithms

  • Lekh Raj Vermani, Shalini Vermani(Authors)
  • 2019(Publication Date)
  • WSPC (EUROPE)

    (Publisher)

  complete have an interesting property that if one of these is solvable in polynomial time, then every other problem in the class is solvable in polynomial time (cf. [5]).

  Most problems that have been considered so far in the earlier chapters are in P. In this chapter, our effort is to study and identify NP-complete problems.

  15.1.Classes P, NP and NP-Complete

  Problems that are solvable in polynomial time form the class P. Thus

  For example, given a weighted graph G and two vertices u, v of G, finding the shortest path from u to v (i.e., a path from u to v such that the sum of the weights of edges on the path is shortest among weights of all paths from u to v) is a problem in P. Finding product of two square matrices of order n is another problem in P.

  The class NP consists of those problems that are verifiable in polynomial time. So

  If X is a problem that can be solved in polynomial time, then any certificate/proposed solution for this problem can also be verified in polynomial time. Thus P is a subclass of NP (i.e., P ⊆ NP).

  We next consider two other examples of problems in NP.

  Problem 15.1 (Hamiltonian Cycle Problem or HC). Let G = (V, E) be a given connected graph. A simple cycle in G is called a Hamiltonian cycle if it traverses each vertex of G exactly once. “Does G have a Hamiltonian cycle?” is called the Hamiltonian Cycle Problem or just HC . A certificate for this problem shall be a sequence (v1 , v2 , . . . , v

  n

  ) of vertices of G with |V | = n. It can be verified in polynomial time if the edges (v

  i

  , v

  i+1

  ) for 1 ≤ i ≤ n − 1 and (v

  n

  , v1 ) are in E. If the graph is represented by the adjacency lists, all that we need to check is if v

  i+1

  ∈ adj(v

  i

  ) for 1 ≤ i ≤ n − 1 and v1 ∈ adj(v

  n

  ), i.e., a total number of almost n comparisons. This proves that HC is an NP-problem

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  The Golden Ticket

  P, NP, and the Search for the Impossible

  • Lance Fortnow(Author)
  • 2013(Publication Date)
  • Princeton University Press

    (Publisher)

  “NP-complete” quickly became the standard terminology. It took Donald Knuth about four decades to finish volume 4.

  Knuth should have pushed a bit harder for less technical names for “NP-complete,” and perhaps for “P” and “NP” as well. The P versus NP problem has taken on an importance that goes well beyond computer science, and using terminology that just abbreviates a technical definition hides this import from outsiders. But terminology gets embedded in the culture over the decades, and at this point it would be difficult to change, even if we had great alternatives.

  Knuth also realized that all this fuss to come up with a name would be wasted if in fact P = NP, since then the NP-complete problems would be just the ones in P. But Knuth was “willing to risk such an embarrassment, and in fact I’m willing to give a prize of one live turkey to the first person who proves that P = NP.” So prove P = NP and you will win a million dollars and a turkey.

  Beyond Karp

  After Karp’s paper, an industry in computer science arose showing the NP-completeness of a large variety of search problems. Over the next several years, many professors and grad students took a number of known search problems (as well as some new ones) and showed them to be NP-complete. A classic 1979 book* lists over three hundred major NP-complete problems. NP-complete problems continually arise in computer science, physics, biology, economics, and many other areas that reach that pinnacle of hardness. A Google Scholar search on “NP-Complete” returns over 138,000 scientific articles from 1972 to 2011, nearly 10,000 in 2011 alone. We can’t list all of them here, but let me give you a flavor of some of them.

  Dominating Set

  Are there fifty people in Frenemy such that everyone else is friends with at least one of them? NP-complete.

  Partition into Triangles

  The dorm rooms of the Frenemy Institute can each hold three students. Can we assign the students to dorm rooms such that no enemies end up in the same room? NP-complete.

  Sign up to read

  Learn more about book