NP Hard Problems

7 Key excerpts on "NP Hard Problems"

• 

  eBook - ePub

  CAD of Circuits and Integrated Systems

  • Ali Mahdoum(Author)
  • 2020(Publication Date)
  • Wiley-ISTE

    (Publisher)

  Based on these definitions, the following can be noted:

  • – an NP-hard problem (D) is at least as difficult as an NP-complete problem (C), as the resolution of C can be done through that of D;
  • – according to the literature, an NP-hard problem can belong or not to the class NP (see Figure 1.6 ; it is however ambiguous for a problem that does not belong to NP to be called NP-hard);
  • – since there is a polynomial transformation for any pair of NP-complete problems, all the NP-complete problems can be polynomially reduced to an NP-hard problem, through which the polynomial Turing reduction of one of these NP-complete problems was done;
  • – if the decision problem associated with a P problem is NP-complete, then P is NP-hard;
  • – according to the conjecture P ≠ NP, an NP-hard problem cannot reach the exact solution within polynomial time (NP-hard problems are the most difficult in the class NP).

  Figure 1.6.

  Classification (according to the literature) of NP-hard problems

  Examples of NP-hard problems:

  • – The search problem P2 of assigning 0 and 1 to the variables of a logical function giving it possibly the value 1 is NP-hard because the decision problem P1 associated with it is NP-complete. Indeed, if an assignment rendering the logical function true can be found (or not), we could answer YES (respectively NO) to the question: Is there an assignment of 0 and 1 to variables of E giving it the value 1? The answer to this question would be in polynomial time assuming that the search for the assignment has the complexity O(1). Therefore, P1 αT P2 . It is worth noting that the computational complexity of P2 is not polynomial; therefore, it is not O(1). It is simply a manner of finding out whether the resolution of P1 (via P2 ) would take a polynomial time assuming the complexity of P2 is constant.
  • – The traveling salesman problem P2 is NP-hard. Indeed, if we could find an optimal Hamiltonian circuit of a certain cost C, the associated decision problem P1 could be solved: Is there a cycle of length ≤ B in a graph G=(V,E)? If the Hamiltonian circuit does not exist, the answer to the decision problem is NO. Otherwise, the comparison between B and C leads to answering YES or NO to problem P1 . Obtaining YES or NO therefore takes a polynomial time assuming that the resolution of P2 is done in O(1). Consequently, P1 αT P2

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

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

  Concepts of Combinatorial Optimization

  • Vangelis Th. Paschos, Vangelis Th. Paschos(Authors)
  • 2014(Publication Date)
  • Wiley-ISTE

    (Publisher)

  is a (polynomial) Turing reduction.

  A problem that fulfills condition 2 of definition 1.4 (without necessarily checking condition 1) is called NP-hard5 . It follows that a decision problem Π

  is NP-complete if and only if it belongs to NP and it is NP-hard

  .

  With the class NP-complete, we can further refine (Figure 1.2 ) the world of NP. Of course, if P = NP, the three classes from Figure 1.2 coincide; moreover, under the assumption P ≠ NP, the classes P and NP-complete do not intersect.

  Let us denote by NP-intermediate the class NP\ (P∪NP – complete ). Informally, this concerns the class of problems of intermediate difficulty, that is problems that are more difficult than those from P but easier than those from NP-complete. More formally, for two complexity classes C and C′ such that C′ ⊂ C, and a reduction preserving the membership of C′, a problem is C-intermediate if it is neither C-complete under , nor belongs to C′. Under the Karp reduction, the class NP-intermediate is not empty [LAD 75].

  Let us note that the idea of NP-completeness goes hand in hand with decision problems . When dealing with optimization problems, the appropriate term, used in the literature, is

  NP-hard6 . A problem of NPO is NP-hard if and only if its decisional variant is an NP-complete

  problem.

  Figure 1.2 .

  P, NP and NP-complete (under the assumption P

  ≠

  NP)

  The problem sat was the first problem shown to be NP-complete (the proof of this important result can be found in [COO 71]). The reduction used (often called generic reduction ) is based on the theory of recursive languages and Turing machines (see [HOP 79, LEW 81] for more details and depth on the Turing machine concept; also, language-problem correspondence is very well described in [GAR 79, LEW 81]). The general idea of generic reduction, also often called the “Cook–Levin technique (or theory)”, is as follows:

  For a generic decision (language) problem belonging to NP

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Paradigms of Combinatorial Optimization

  Problems and New Approaches

  • Vangelis Th. Paschos, Vangelis Th. Paschos(Authors)
  • 2014(Publication Date)
  • Wiley-ISTE

    (Publisher)

  4 and chapters devoted to PCP, inapproximability results, and complexity classes of optimization problems. The books by Papadimitriou [PAP 94], by Vazirani [VAZ 01] and by Arora and Barak [ARO 09] have chapters devoted to inapproximability results.

  13.2. Some technical preliminaries

  We assume that the reader is familiar with the basic notions of algorithms, running time and big-Oh notation. Such background can be found, for example, in the introductory chapter of Papadimitriou’s textbook [PAP 94].

  NP-Completeness

  We assume that all combinatorial objects that we refer to (graphs, Boolean formulas, families of sets) are represented as binary strings. We denote the length of a binary string x by |x |. We represent a decision problem as a language, that is as the set of all inputs for which the answer is YES. We define P as the class of languages that can be decided in polynomial time. We define NP as the class of languages L such that there is a polynomial time computable predicate V and a polynomial q () such that x ∈ L if and only if there is w , |w | q (|x |), such that V (x , w ) accepts. We think of w as a proof or witness that x is in the language.

  For two languages L 1 and L 2 , we say that L 1 reduces to L 2 , and we write L 1 m L 2 if there is a polynomial time computable f such that x ∈ L 1 if and only if f (x ) ∈ L 2 . A language A is NP-hard if every language L in NP reduces to A . A language is NP-complete if it is NP-hard and it belongs to NP.

  NPO problems

  A combinatorial optimization problem O is defined5 by a cost function costO () such that given an instance x of the problem and a solution s , outputs costO (x , s ), which are either the cost of the solution (a non-negative real number) or the special value ⊥ if s is not a feasible solution for x . For every x , there is only a finite number of feasible solutions s such that costO (x , s ) ⊥. If O is a maximization problem (respectively minimization ) then our goal is, given x , to find a feasible solution s such that cost(x , s ) is smallest (respectively largest). We denote by optO (x ) the cost of an optimal solution for x

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Paradigms of Combinatorial Optimization

  Problems and New Approaches, Volume 2

  • Vangelis Th. Paschos, Vangelis Th. Paschos(Authors)
  • 2013(Publication Date)
  • Wiley-ISTE

    (Publisher)

  4 and chapters devoted to PCP, inapproximability results, and complexity classes of optimization problems. The books by Papadimitriou [PAP 94], by Vazirani [VAZ 01] and by Arora and Barak [ARO 09] have chapters devoted to inapproximability results.

  13.2. Some technical preliminaries

  We assume that the reader is familiar with the basic notions of algorithms, running time and big-Oh notation. Such background can be found, for example, in the introductory chapter of Papadimitriou’s textbook [PAP 94].

  NP-Completeness

  We assume that all combinatorial objects that we refer to (graphs, Boolean formulas, families of sets) are represented as binary strings. We denote the length of a binary string x by |x| . We represent a decision problem as a language, that is as the set of all inputs for which the answer is YES. We define P as the class of languages that can be decided in polynomial time. We define NP as the class of languages L such that there is a polynomial time computable predicate V and a polynomial q () such that x ∈ L if and only if there is w , |w| q (|x| ), such that V (x, w ) accepts. We think of w as a proof or witness that x is in the language.

  For two languages L 1 and L 2 , we say that L 1 reduces to L 2 , and we write L 1

  m L

  2 if there is a polynomial time computable f such that x ∈ L 1 if and only if f (x ) ∈ L 2 . A language A is NP-hard if every language L in NP reduces to A . A language is NP-complete if it is NP-hard and it belongs to NP.

  NPO problems

  A combinatorial optimization problem O is defined5 by a cost function costO () such that given an instance x of the problem and a solution s , outputs costO (x, s ), which are either the cost of the solution (a non-negative real number) or the special value ⊥ if s is not a feasible solution for x . For every x , there is only a finite number of feasible solutions s such that costO (x, s ) ≠ ⊥. If O is a maximization problem (respectively minimization ) then our goal is, given x , to find a feasible solution s such that cost(x, s ) is smallest (respectively largest). We denote by optO (x ) the cost of an optimal solution for x

  Sign up to read

  Learn more about book