P vs NP

11 Key excerpts on "P vs NP"

• 

  No longer available |Learn more

  C++ Data Structures and Algorithm Design Principles

  Leverage the power of modern C++ to build robust and scalable applications

  • John Carey, Shreyans Doshi, Payas Rajan(Authors)
  • 2019(Publication Date)
  • Packt Publishing

    (Publisher)

  non-deterministic polynomial time .

  The relationship between these classes of problems is a subject of considerable debate. The particular matter of interest is that the complexity of computation that's required to verify their solutions is "easy," whereas the complexity of producing solutions is "hard". This demonstrates one of the most widely discussed unsolved problems in programming: does the fact that the verification of solutions is in class P imply that there is also an approach for producing solutions in polynomial time? In other words, does P = NP ? While the generally postulated answer to this question is no (P ≠ NP ), this has yet to be proven, and doing so (regardless of what the answer actually is) would be a truly revolutionary advance in the study of algorithms and computation.

  Arguably the most interesting group of problems in NP are known as NP-complete because they share a remarkable trait: should a solution be discovered that solves any one of these problems efficiently (that is, in polynomial time), that solution can, in fact, be modified to solve all of the other problems in NP efficiently. In other words, if a polynomial solution for the first example (known as the Boolean satisfiability problem , or SAT ) was found, some variant of the same logic could also be used to solve the second example (known as the graph-coloring problem ), and vice versa.

  Keep in mind that not every exponentially complex problem fits into this classification. Consider the problem of determining the next best move in a chess game. You may describe the recursive logic as follows:

  Sign up to read

  Learn more about book
• 

  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)

  161 C H A P T E R 8 Classes NP and NP -Complete 8.1 THE CLASS NP (NONDETERMINISTIC POLYNOMIAL) Most of the problems met in the standard computer science curriculum are in the class P , defined in Chapter 3 (see Definition 3.6), of problems that have polynomial solutions. One spends a lot of time in classes in data structures and algorithms analysis considering whether an algorithm is of order n 2 , n 3 , n ln n, and so on. You might note that one often dealt with search problems, and in this class, we are dealing with decision prob-lems—not “What is the shortest path?” but “Is there a path from A to B shorter than L?” Now, we introduce a class of problems, NP , which (almost certainly— more about this later) do not have polynomial solutions. You should be asking yourself while you read this chapter: Do I understand what makes a problem belong to the class NP ? Can I show that a problem is in NP ? What kinds of problems are in NP ? What problems are not in NP ? Do I know they are not in NP ? If I were given the task of writing an algorithm for a problem in NP , what are my options? 8.2 DEFINITION OF P AND NP Recall the definition of P —those decision problems that are easy to solve. 162 ◾ Limits of Computation Definition 8.1 The class P is the set of all decision problems that have polynomial solu-tions (that is, they are in O (p(n)) for some polynomial p in the size of the input n). In contrast, NP will consist of problems that are not easy to solve (though no one has been able to prove this!), but which have solutions that are easy to check. There are two standard ways to define the class NP . Nothing mathe-matical should have two definitions, but these two definitions are equiva-lent. So, we will give both, and immediately show that they are equivalent. Sometimes it will be easier to use one definition than the other, so it will be useful to have both available. Note that a yes instance of a decision problem can have a certificate .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Computer Science, Algorithms and Complexity

  • Adele Kuzmiakova(Author)
  • 2020(Publication Date)
  • Arcler Press

    (Publisher)

  The idea of polynomial has led to the generation of complexity classes in this theory. The relevant classes include class p, NP, ZPP, RP, BPP, and BQP. 2. The Complexity Class P: It is a compact class producible by a deterministic Turing machine; it is a collection of decision problems with the possibility of being solved by a deterministic machine in polynomial time. It is built on the intuition that worst case scenarios can be solved. P computation problems are therefore often solvable with efficiency. Problems solvable in the theoretical sense but not in the practical sense are commonly referred to as intractable. There exist problems in P which are intractable in practical terms and may require a number of operations in order to be solved. P encompasses many natural problems, including some versions of linear programming, shortest path problem, and finding a maximum matching in a string. For P problems O (ny), the algorithm solves an instance of size n for the integer y. 3. The Complexity Class NP: In computational complexity theory, NP stands for non-deterministically polynomial and is a set of decision problems solvable in polynomial time on a non-deterministic Turing machine. It brings forth the ideology of non-deterministic algorithms. They are problems verifiable by a deterministic Turing machine in the worst-case polynomial time. All the problems in this class have the property that their solutions can be checked effectively. This class contains many problems that scientists would like to solve, they including The Boolean satisfiability problem, and the Hamiltonian path problem, the vertex cover problem. These decision problem or Computer Science, Algorithms and Complexity 42 instances are computed using an algorithm by a nondeterministic turning machine in the following way. It begins with a guess about the solution produced in a non-deterministic way, in the second part a deterministic algorithm verifies if the guess is a solution to the problem.

  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)

  Multivariate polynomials of degree 3 over F 2 that have a root (namely, an assignment to the variables on which it evaluates to 0). Figure 5. Which of these graphs are Hamiltonian? Which pairs of these graphs are isomorphic? It is evident that decision problems in P are also in NP . The verifier V C is simply taken to be the efficient algorithm for C , and the witness y can be the empty sequence. Corollary 3.4. P ⊆ NP . But can we solve all NP problems efficiently? Can we vastly improve the trivial “brute-force” exponential time algorithm mentioned above to polynomial time for all NP problems? This is the celebrated P vs. NP question. Open Problem 3.5. Is P = NP ? The definition of NP , and the explicit P = NP ? question (and much more that we will soon learn about) appeared formally first (independently and in slightly 11 This problem is a special case of the well-known “Traveling Salesman Problem” (TSP), seeking the shortest such tour in a graph with edge lengths given. 28 COMPLEXITY 101, P AND NP different forms) in the papers of Cook [Coo71] and Levin [Lev73] in the early 1970s, one researcher in America and the other in the Soviet Union. However, both the definition and question appeared informally earlier, again independently in the East and West, but with similar motivations. They all struggle with the tractability of solving problems for which finite algorithms exist, including finding finite proofs of theorems, short logical circuits for Boolean functions, isomorphism of graphs, and a variety of optimization problems of practical and theoretical interest. In all these examples, exhaustive search was an obvious but exponentially expensive solution, and the goal of improving it by a possibly more clever (and faster) algorithm was sought, hopefully one of polynomial complexity (namely, in P ).

  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)

  This notion of easy to verify, but not necessarily easy to solve decision problems is at the heart of the Class NP. Specifically, NP includes all those decision problems that could be polynomial-time answered if the right (polynomial-length) clue or guess was appended to the problem input string. The associated verifying Turing machine takes both the problem encoding and the clue string as input. Whenever the correct conclusion for an instance is yes, there must exist some clue that will cause this Turing machine to halt with the answer yes. Naturally, there must also be no clue that would cause the same Turing machine to halt with the answer yes when the correct response is no. The letters NP denote nondeterministic polynomial. This terminology derives from the fact that problems in NP are nondeterministically polynomial-time solvable in the sense that a suitable random proof gener-ator has some positive probability of guessing a polynomial-length proof of yes whenever the correct response is yes. 26 2 Computational Complexity Persons accustomed to working in discrete optimization are likely to find it more natural to adopt the equivalent conceptualization that prob-lems in NP are ones that can be solved by total enumeration of some polynomial-length decision vector. If we totally enumerate the possible clue strings and apply the Turing machine verification algorithm to each possibility, we must ultimately encounter a string that leads to a yes conclusion when one exists. The Class NP certainly contains the Class P, the set of decision problems that are polynomial-time solvable without benefit of a clue. But NP also includes a great many problems not known to belong to P. In fact, NP contains the decision problem analogs of virtually all popular discrete optimization problems.

  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)

  An explanation is due on the use of the words “efficient algorithm.” … I am not prepared to set up the machinery necessary to give it formal meaning, nor is the present context appropriate for doing this. … For practical purposes the difference between algebraic and exponential order is more crucial than the difference between [computable and not computable]. … It would be unfortunate for any rigid criterion to inhibit the practical development of algorithms which are either not known or known not to conform nicely to the criterion. … However, if only to motivate the search for good, practical algorithms, it is important to realize that it is mathematically sensible even to question their existence.

  Edmonds’s algebraic order is exactly P, the problems we can compute efficiently. As Edmonds suggests, we need a formal notion to define problems like whether P = NP, but we should keep in mind a more informal notion of efficient computation, a point of view I try to follow in this book.

  Cobham independently defined P and talks about why the notion is a good one.

  For several reasons, the class P seems a natural one to consider. For one thing, if we formalize the definition relative to various general classes of computing machines we seem always to end up with the same well-defined class of functions. Thus we can give a mathematical characterization of P having some confidence it characterizes correctly our informally defined class.

  As with the definition of computability, the class P does not depend on the specific details of the computational model. Cobham also offers a caution:

  The problem is reminiscent of, and obviously closely related to, that of the formalization of the notion of effectiveness. But the emphasis is different in that the physical aspects of the computation process are here of predominant concern.

  Perhaps Cobham realized there might be future models of computation that may not correspond to his class P. Later developments in randomized and quantum computation will show that perhaps we cannot have a fixed notion of efficient computation.

  Then in 1971 came Steve Cook’s paper that defined NP, the problems we can verify efficiently, the P versus NP problem, and the first NP-complete problem. A year later Richard Karp gave his paper showing that a number of important problems were NP-complete.

  In 1972 the IBM T. J. Watson Research Center hosted the Symposium on the Complexity of Computer Computations, a meeting mostly remembered for Karp’s presentation of his paper. The organizers of the meeting held a panel discussion at the end of the symposium on the future of the field. One of the questions asked was, “How is the theory developing from originally being a scattering of a few results on lower bounds and some algorithms into a more unified theory?” The panelists, including Karp himself, were at best only vaguely aware that the answer lay in Cook’s and Karp’s papers with the concepts of P, NP, reducibility, and what would later be called NP-completeness.

  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)

  So the idea behind the theoretical concept of nondeterministic algorithms and their superior performance on a nondeterministic machine, when compared to deterministic algorithms, helps rephrase the definition of many problems belonging to the NP class. Thus, there exist many NP class problems whose best-known deterministic algorithms that yield exponential time complexity, are solvable on a nondeterministic machine using nondeterministic algorithms having polynomial time complexity. i = choice([1:n]) if (A[i] == X) then print( ‘ element X found’); success print(‘element X not found’) failure. 292 A Textbook of Data Structures and Algorithms 3 If the P class alludes to problems with deterministic algorithms having polynomial time complexity when run on deterministic machines, the NP class alludes to problems with nondeterministic algorithms having polynomial time complexity when run on nondeterministic machines. In light of the above, P class and NP class are defined as below: P class This is a class of decision problems that can be solved in polynomial time by deterministic algorithms. NP class This is a class of decision problems that can be solved by nondeterministic polynomial time algorithms, where verification of the solution can be done in polynomial time. Most decision problems are in NP and 𝑃 ⊆ 𝑁𝑃, since the deterministic algorithm that solves the problem belonging to the P class can be used to verify the solution in polynomial time after ignoring the nondeterministic guessing of the candidate solution, both of which are hallmarks of nondeterministic algorithms. 22.3. Satisfiability problem The satisfiability problem picked from the domain of logic, typically propositional logic or propositional calculus, is a simple problem that has found itself significantly linked to the concept of NP-completeness. The problem and its nondeterministic algorithm are detailed here.

  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

  Goedel's Way

  Exploits into an undecidable world

  • Gregory Chaitin, Francisco A Doria, Newton C.A. da Costa(Authors)
  • 2011(Publication Date)
  • CRC Press

    (Publisher)

  (The length G¨ odel’s Way 99 of a string is the number of 0s and 1s in it; given a bit string x , its length is noted | x | , and the bound may be noted | x | n + n .) Now let’s explain the name of the problem. P stands for “polynomial,” and NP for “nondeterministic polynomial.” Think of the traveling salesman prob-lem. Suppose that given N cities, there are some N ! possible routes to check. If there is a Turing machine that branches out and performs N ! computations in paralell, at the same time, the obvious algorithm for TSP is to test each one of the possible N ! routes with that massively parallel machine. That can be made as fast as one tests for a single route, and one can easily see that this is time-polynomial (suffices to add the length of the connecting roads between adjacent cities). The NP class of problems and the P = NP conjecture We insist: NP stands for “nondeterministic polynomial”; we’ll comment again on its meaning of that at the end of this paragraph. Problems in the NP class are described by the slogan: If you know the solution for a problem in NP then you can test (check) it very fast. However if you don’t know the solution then it is very hard (it takes a long long time) to get one solution in the general case. More precisely: they are easy to check because they can be checked by a poly machine (a time-polynomial machine). They are hard to find because in the general case nobody knows an algorithm for it which is polynomial, i.e., can be implemented by a poly machine. Then follows the P = NP question (this equation means, NP problems are solvable by poly machines): Is there a poly machine that settles all instances of NP problems? Recall that the so-called nondeterministic poly (that is, NP –) machines can settle any NP problem in polynomial time, as described above, whereas the use of NP to denote that class of problems. If there is no such an algorithm, then P = NP is false.

  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)

  Conversely, the algorithm says NO if all the possible final states are non-accepting. Clearly, this computational paradigm is at least as efficient as the conventional (deterministic) model that does not permit any guesses. However, the obvious question is - does it provide us with any provable advantage? We can relate it to our earlier Prover /Verifier game in the following manner. The Prover will guess the solution using its magical non-deterministic power and the Verifier verifies using conventional computation. While the verifier is limited by polynomial time, there is no such constraint on the Prover, so we can think about the class N P as those problems for which verification of solutions can be done in polynomial time. Although, N P doesn’t correspond to any realistic computational model, it has been very useful to characterize the important property of efficient verification and has also helped us discover relationship between problems from diverse domains like graphs, number theory, algebra, geometry, etc. In this chapter we will look at many such problems. A deterministic model can emulate this by trying out all possible guesses but it has to pay a huge price for this. Even for two guesses per move, for n moves of the non-deterministic machine, we may have to try 2 n moves. However, this doesn’t rule out more efficient emulations or more clever transformations which is one of the central theme of research in this area. 1 The reader should not confuse it with a probabilistic model where a guess is made according to some probability distribution. NP Completeness and Approximation Algorithms 233 More formally, we define the class P = ∪ i≥1 C (T D (n i )) where C (T D (n i )) denotes problems for which O(n i ) time deterministic algorithms can be designed. Analogously, N P = ∪ i≥1 C (T N (n i )) where T N () represents non-deterministic time. From our previous discussion it is obvious that P ⊆ N P .

  Sign up to read

  Learn more about book
• 

  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