NP Hard Problems

9 Key excerpts on "NP Hard Problems"

• 

  eBook - PDF

  Limits of Computation

  An Introduction to the Undecidable and the Intractable

  • Edna E. Reiter, Clayton Matthew Johnson(Authors)
  • 2012(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  But why are NP -hard problems not easy? Why call them intractable? This brings us to the boundaries of computer science knowledge. There is no known polynomial algorithm for any NP -hard problem. However, it has never been shown—and will (almost certainly) never be shown that NP -hard problems do not have polynomial solutions. The famous incompleteness theorem of Kurt Godel shows that any theory will have some statements that are true but can never be proved, and (most) computer scientists think that the nonexistence of polynomial solutions for NP -hard problems is in this category. In other words, it is believed that no one will find a polynomial time algo-rithm for any NP -hard problem. It is also believed that no one will prove that a polynomial time algorithm does not exist. The person who can do either one of these—find a polynomial algorithm for some NP -hard prob-lem or show that one cannot exist—will be immediately famous, at least in the world of theoretical computer science. See the Web site referenced in Exercise 11 at Claymath.org for a temptation to take on this problem. If either of these is achieved, the whole theory of complexity will essen-tially collapse, and the phrases NP -hard and NP -complete never again be mentioned in any computer science class, except perhaps in passing refer-ence to the ignorance of the ancients. Classes NP and NP -Complete ◾ 171 To reiterate the important points: (1) no NP -hard problem has a known polynomial algorithm, but (2) we cannot show that no polynomial algo-rithm exists. 8.7 A FIRST NP -COMPLETE PROBLEM: BOOLEAN SATISFIABILITY So far, we have defined NP -complete and NP -hard, but have given no examples. The first example, and the proof that the problem is in these two classes, is basic to all further discussion.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  A Textbook of Data Structures and Algorithms, Volume 3

  Mastering Advanced Data Structures and Algorithm Design Strategies

  • G. A. Vijayalakshmi Pai(Author)
  • 2022(Publication Date)
  • Wiley-ISTE

    (Publisher)

  Thus, the satisfiability problem, which has exponential time complexity over a deterministic machine, reports polynomial time complexity on a nondeterministic machine. Therefore, the satisfiability problem belongs to the NP class. 22.4. NP-complete and NP-hard problems The NP class was introduced as a class of problems to which the best-known algorithms to date report exponential time complexity. Also, these problems do not show evidence that polynomial time algorithms do not exist for them either. However, the best thing is that many of the problems for which no polynomial time algorithm exists, seem to be computationally related establishing two classes of problems, for example, NP-complete and NP-hard. 298 A Textbook of Data Structures and Algorithms 3 Figure 22.1. Nondeterministic algorithm for the satisfiability problem An NP-complete problem is one that can be solved in polynomial time if all other NP-complete problems can also be solved in polynomial time. An NP-hard problem is one which, if solvable in polynomial time, then all other NP-complete problems can be solved in polynomial time. Thus, all NP-complete problems are NP-hard but all NP-hard problems are not NP-complete. The formal definitions that describe NP-completeness are listed in the next section. 22.4.1. Definitions 22.4.1.1. Problem reducibility Let X and Y be two problems. X reduces to Y, denoted as X ∝ Y if there is a method to solve X by a deterministic polynomial time algorithm using a deterministic algorithm that solves Y in polynomial time. It can be proved that problem reducibility satisfies the transitivity property. Thus, if X ∝ Y and Y ∝ Z then X ∝ Z. 22.4.1.2. NP-hard problem The problem X is NP-hard if the satisfiability problem reduces to X, that is, SAT ∝ X. 22.4.1.3. NP-complete problem A problem X is NP-complete if X is NP-hard and X ∈ 𝑁𝑃.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Discrete Optimization

  • R. Gary Parker, Ronald L. Rardin(Authors)
  • 2014(Publication Date)
  • Academic Press

    (Publisher)

  Problems to which all members of NP polynomially reduce are called NP-Hard. Although none is even close to being solved polynomially, it has turned out that the family of AT-Hard problems is amazingly rich. It includes, in particular, virtually all the problems that have frustrated dis-crete optimizers for decades. A very partial list would include traveling salesman, graph-coloring, precedence constrained scheduling, parallel-pro-cessor scheduling, knapsack, set covering/packing/partitioning, various fixed charge models, and 0 — 1 integer/mixed-integer programming. 2.3 NP-Equivalent Problems 29 The key to the discovery of so many NP-Hard problems, and indeed the seminal development of all recent complexity theory was achieved by Stephen Cook (1971). Cook showed that a particular problem in logic, known as the Satisfiability Problem, was NP-Hard. This result started the wheel in motion, and Richard Karp's (1972) work provided real momen-tum by demonstrating the reducibility of satisfiability to various well-known problems in the discrete optimization literature. As suggested, the satisfiability problem is one that is perhaps more nearly suited for the domain of the logician than say the operation researcher. Define a set of Boolean variables {x x ,x 2 , · . · , x n ) and let the comple-ment of any of these variables x t be denoted by jc,·. In the language of logic, these variables are referred to as literals. To each literal we assign a label of true ox false such that x t is true if and only if x t {{false. Using standard notation where the symbol V denotes or and is the symbol for and, we can write any Boolean expression in what is referred to as conjunctive normal form, i.e., as a finite conjunction of disjunctions using each literal once at most.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Algorithms: Design Techniques And Analysis

  Design Techniques and Analysis

  • M H Alsuwaiyel(Author)
  • 1999(Publication Date)
  • World Scientific

    (Publisher)

  It turns out that many of the interesting real world problems do not fall into this category, as their solution requires an amount of time that is measured in terms of exponential and hyperexponential functions, e.g. 2n and n!. It has been agreed upon in the computer science community to refer to those problems for which there exist polynomial time algorithms as tractable, and those for which it is unlikely that there exist polynomial time algorithms as intractable. In this chapter, we will study a subclass of intractable problems, com- monly referred to as the class of NP-complete problems. This class contains, among many others, hundreds of well-known problems having the common property that if one of them is solvable in polynomial time, then all the others are solvable in polynomial time. Interestingly, many of these are natural problems in the sense that they arise in real world applications. Moreover, the running times of the existing algorithms to solve these prob- lems are invariably measured in terms of hundreds or thousands of years 279 280 NP- Complete Problems for inputs of moderate size (see Table 1.1 on page 24). When studying the theory of NP-completeness, it is easier to restate a problem so that its solution has only two outcomes: yes or no. In this case, the problem is called a decision problem. In contrast, an optimization prob- lem is a problem that is concerned with the minimization or maximization of a certain quantity. In the previous chapters, we have encountered numer- ous optimization problems, like finding the minimum or maximum in a list of elements, finding the shortest path in a directed graph and computing a minimum cost spanning tree of an undirected graph. In the following, we give three examples of how to formulate a problem as a decision problem and an optimization problem. Example 10.1 Let S be a sequence of real numbers. The ELEMENT UNIQUENESS problem asks whether all the numbers in S are distinct.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Techniques for Designing and Analyzing Algorithms

  • Douglas R. Stinson(Author)
  • 2021(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 9

  Intractability and Undecidability

  DOI: 10.1201/9780429277412-9

  In this chapter, we present the theory of NP-completeness, which is an attempt to categorize decision problems as tractable (i.e., solvable in polynomial time) or intractable. We define complexity classes, including P, NP and NPC, which are abbreviations (respectively) for polynomial, non-deterministic polynomial, and NP-complete. We give proofs that a number of familiar problems are NP-complete. We also extend the analysis of intractability to include NP-hard problems, which are not required to be decision problems. Approximation algorithms are considered as a way to deal with NP-hard problems in practice. Finally, we briefly address the concept of undecidable problems, which are problems that cannot be solved by any algorithm.

  9.1 Decision Problems and the Complexity Class P

  One of the main goals of computer science is to determine which problems can be solved in polynomial time. It turns out that there is a large class of problems (the NP-complete problems), which are equivalent in the sense that either they all can be solved in polynomial time, or none of them can be solved in polynomial time. It is widely believed, though not proven, that none of the NP-complete problems can be solved in polynomial time. The NP-complete problems include many familiar problems of practical interest.

  In this chapter, we develop the theory of NP-completeness, which is based on decision problems. A decision problem is any problem in which the solution is an answer of the form

  y e s

  or

  n o

  . That is, given a problem instance I, there is a question that is to be answered

  y e s

  or

  n o

  . Thus we can classify every problem instance I of a decision problem as being a yes-instance (if the correct answer is

  y e s

  ) or a no-instance (if the correct answer is

  n o

  .).

  An algorithm for a decision problem is not required to specify a “solution” to a problem. It just has to reply

  y e s

  or

  n o

  correctly. Therefore, an algorithm A is said to solve a decision problem Π provided that A finds the correct answer (

  y e s

  or

  n o

  ) for every instance I of Π

  Sign up to read

  Learn more about book
• 

  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 - PDF

  Mathematics and Computation

  A Theory Revolutionizing Technology and Science

  • Avi Wigderson(Author)
  • 2019(Publication Date)
  • Princeton University Press

    (Publisher)

  4 Problems and classes inside (and around) NP This chapter touches on different aspects and variants of the P vs. NP question studied in computational complexity, the resulting complexity classes in the neigh-borhood of these two main classes, and the central questions about them. The first brief section lists a few types of problems that are not classification problems, leading mostly to classes containing NP . The remaining sections are devoted to problems and classes in the potentially vast universe between the easiest and hard-est problems in NP , namely, between P and NP -complete. We discuss degrees of intermediate complexities of problems in this universe, as well as constraint sat-isfaction problems (CSPs), for which there may be no such middle ground. The last two sections discuss the same universe from another perspective, motivated by average-case analysis of computational complexity as well as the more stringent computational needs of cryptography. 4.1 Other types of computational problems and complexity classes There are many other types of computational problems that do not fall into the class NP , arise naturally, and are studied intensively in both theory and practice. Some of the most natural types are: • Optimization problems. Fix an NP problem and a cost function on solu-tions (witnesses). Given an input, find the best solution for it (e.g., find the largest clique, the shortest path, the minimum energy configuration). A natu-ral relaxation of optimization problems asks for an approximation, namely to find a solution that is “close” to the best one. A complexity theory allowing the understanding of the limits of efficient approximation has been one of the most exciting developments in computational complexity, starting with the PCP Theorem 10.6. These problems are discussed in Sections 4.3 and 10.3.

  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)

  Chapter 15

  NP-Complete Problems

  Most of the algorithms we have studied so far were polynomial-time algorithms, i.e., algorithms having time complexity O(n

  k

  ) where n is the size of the input instance and k is a constant positive integer. However, not all problems can be solved in polynomial time — there do indeed exist such problems as cannot be solved in polynomial time. Problems that are solvable by polynomial-time algorithms are called easy or tractable. Those problems that cannot be solved by polynomial-time algorithms are called hard or intractable.

  There do exist several problems which are not solvable by polynomial-time algorithms. For example, the Traveling Salesman Problem involving n cities to be visited is one such. There is no algorithm which solves this problem in general and the only way to solve it is by brute force. There are (n − 1)! possible tours, we need to find the cost for each tour and then to look for a tour with minimum cost. Therefore solving this problem by brute force requires (n − 1)! computations. Observe that (n − 1)! > 2

  n

  for all n ≥ 6 and, so, the time complexity for such a solution is even more that exponential.

  In general, there are three types of problems — P, NP and NP-complete. There is another class of problems, i.e., Co-NP but we do not consider these here (although we may define this class). Every problem in class P is in class NP but “is every problem in class NP in class P” is still an interesting open problem. Problems in the class NP-complete are in the class NP and are the most difficult ones in the class NP. The problems in the class NP-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

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Design and Analysis of Algorithms

  A Contemporary Perspective

  • Sandeep Sen, Amit Kumar(Authors)
  • 2019(Publication Date)
  • Cambridge University Press

    (Publisher)

  12 C H A P T E R NP Completeness and Approximation Algorithms In the previous chapters we surveyed many well-known algorithmic techniques and successfully applied them to obtain efficient algorithmic solutions for problems from varied domains. Yet, we cannot claim that there is some general methodology for obtaining efficient algorithms for any given problem. To the contrary any new problem often presents unknown challenges that require new insights and the question that is uppermost in anyone’s mind is - what are the problems that are notoriously difficult? We need to first set some target before we can assign a notion of difficulty to a problem. For reasons that will become clear later on, the quest is to design a polynomial time algorithm for any given well-defined problem. This may appear too liberal initially since by definition even n 100 is a polynomial. However, even this has proved elusive for a large number of problems among which we have come across one in the preceding chapters, namely, 0-1 Knapsack problem. Despite promising starts, we could never claim a truly polynomial time algorithm. In addition to fixing the limits of practical computation being a polynomial time algorithm, we need to specify the underlying computational model since that will also affect what is achievable in polynomial time. Fortunately, the notion of polynomial time is a robust concept that is not significantly affected by the choice of computational model, except for some constant factors in the exponent of n. We will discuss about a large class of natural and important problems that admits a characterization, that is very intuitive NP Completeness and Approximation Algorithms 231 and has resulted in a very interesting theoretical framework. Since the reader is familiar with the Knapsack problem, we will illustrate this framework in the context of the Knapsack problem. Consider a Prover , Verifier interactive game regarding any given Knapsack instance.

  Sign up to read

  Learn more about book