NP-complete Concepts

Artificial Intelligence: A Modern Approach

by Stuart Russell and Peter Norvig · 14 Jul 2019 · 2,466pp · 668,761 words

, 1964; Edmonds, 1965). It is important because exponential growth means that even moderately large instances cannot be solved in any reasonable time. The theory of NP-completeness, pioneered by Cook (1971) and Karp (1972), provides a basis for analyzing the tractability of problems: any problem class to which the class of

…

NP-complete problems can be reduced is likely to be intractable. (Although it has not been proved that NP-complete problems are necessarily intractable, most theoreticians believe it.) These results contrast with the optimism with which the

…

to Ernest Kinsey in 1878). Ratner and Warmuth (1986) showed that the general n × n version of the 15-puzzle belongs to the class of NP-complete problems. Rubik’s Cube was of course invented in 1974 by Ernő Rubik, who also discovered an algorithm for finding good, but not optimal solutions

…

partial assignment is one that leaves some variables unassigned, and a partial solution is a partial assignment that is consistent. Solving a CSP is an NP-complete problem in general, although there are important subclasses of CSPs that can be solved very efficiently. 5.1.1Example problem: Map coloring Suppose that, having

…

a value consistent with X1,...,Xi–1. The total run time is only O(n2d). Of course, there is no free lunch: constraint satisfaction is NP-complete in general, and any algorithm for establishing n-consistency must take time exponential in n in the worst case. Worse, n-consistency also requires space

…

depth-first.) Later in this chapter we show algorithms that are much more efficient in many cases. Unfortunately, propositional entailment is co-NP-complete (i.e., probably no easier than NP-complete—see Appendix A), so every known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size

…

that satisfies the sentence. The problem of determining the satisfiability of sentences in propositional logic—the SAT problem—was the first problem proved to be NP-complete. Many problems in computer science are really satisfiability problems. For example, all the constraint satisfaction problems in Chapter 5 ask whether the constraints are satisfiable

…

SAT problems Some SAT problems are harder than others. Easy problems can be solved by any old algorithm, but because we know that SAT is NP-complete, at least some problem instances must require exponential run time. In Chapter 5, we saw some surprising discoveries about certain kinds of problems. For example

…

first-order logic by J. A. Robinson (1965). Stephen Cook (1971) showed that deciding satisfiability of a sentence in propositional logic (the SAT problem) is NP-complete. Many subsets of propositional logic are known for which the satisfiability problem is polynomially solvable; Horn clauses are one such subset. Early investigations showed that

…

“A Critique of Pure Reason” (McDermott, 1987). Selman and Levesque (1993) discuss the complexity of inheritance with exceptions, showing that in most formulations it is NP-complete. Description logics were developed as a useful subset of first-order logic for which inference is computationally tractable. Hector Levesque and Ron Brachman (1987) showed

…

for a 3-SAT problem is #P-complete (“number-P complete”), this means that Bayes net inference is #P- hard—that is, strictly harder than NP-complete problems. There is a close connection between the complexity of Bayes net inference and the complexity of constraint satisfaction problems (CSPs). As we discussed in

…

1, a form of likelihood weighting converges in (randomized) polynomial time (Dagum and Luby, 1997). Shimony (1994) showed that finding the most probable explanation is NP-complete—intractable, but somewhat easier than computing marginals—while Park and Darwiche (2004) provide a thorough complexity analysis of MAP computation, showing that it falls into

…

than this depends on the game being studied: for many classes of cooperative game, the problem of checking non-emptiness of the core is co-NP-complete. We give an example below. Before proceeding, let’s see an example of a superadditive game with an empty core. The game has three players

…

et al., 1984). Hyafil and Rivest (1976) proved that finding an optimal decision tree (rather than finding a good tree through locally greedy selections) is NP-complete. But Bertsimas and Dunn (2017) point out that in the last 25 years, advances in hardware design and in algorithms for mixed-integer programming have

…

size p. There are such subsets; hence the algorithm is exponential in the size of the minimal determination. It turns out that the problem is NP-complete, so we cannot expect to do better in the general case. In most domains, however, there will be sufficient local structure (see chapter 13 for

…

-time algorithms. But this has never been proven. Those who are interested in deciding whether P = NP look at a subclass of NP called the NP-complete problems. The word “complete” is used here in the sense of “most extreme” and thus refers to the hardest problems in the class NP. It

…

has been proven that either all the NP-complete problems are in P or none of them is. This makes the class theoretically interesting, but the class is also of practical interest because many

…

important problems are known to be NP-complete. An example is the satisfiability problem: given a sentence of propositional logic, is there an assignment of truth values to the proposition symbols of the

…

, so if you solved any NP-hard problem, you could solve all the problems in NP. The NP-complete problems are all NP-hard, but there are some NP-hard problems that are even harder than NP-complete. The class co-NP is the complement of NP, in the sense that, for every decision

…

subset of both NP and co-NP, and it is believed that there are problems in co-NP that are not in P. The co-NP-complete problems are the hardest problems in co-NP. The class #P (pronounced “number P” according to Garey and Johnson (1979), but often pronounced “sharp P

…

PSPACE problems—those that require a polynomial amount of space, even on a nondeterministic machine. It is believed that PSPACE-hard problems are worse than NP-complete problems, although it could turn out that NP = PSPACE, just as it could turn out that P = NP. A.2Vectors, Matrices, and Linear Algebra Mathematicians

…

used in computer science today was first introduced in the context of number theory by the mathematician P. G. H. Bachmann (1894). The concept of NP-completeness was invented by Cook (1971), and the modern method for establishing a reduction from one problem to another is due to Karp (1972). Cook and

…

) and Cormen, Leiserson, Rivest and Stein (2009). These books place an emphasis on designing and analyzing algorithms to solve tractable problems. For the theory of NP-completeness and other forms of intractability, see Garey and Johnson (1979) or Papadimitriou (1994). Good texts on probability include Chung (1979), Ross (2015), and Bertsekas and

…

). Fear of heights in infants? Current Directions in Psychological Science, 23, 60–66. Agerbeck, C. and Hansen, M. O. (2008). A multiagent approach to solving NP-complete problems. Master’s thesis, Technical Univ. of Denmark. Aggarwal, G., Goel, A., and Motwani, R. (2006). Truthful auctions for pricing search keywords. In EC-06

…

. K. (1993). EL: A formal, yet natural, comprehensive knowledge representation. In AAAI-93. Hyafil, L. and Rivest, R. (1976). Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5, 15–17. Ieong, S. and Shoham, Y. (2005). Marginal contribution nets: A compact representation scheme for coalitional games. In Proc. Sixth

…

CNF (conjunctive normal form), 244, 244–245, 265, 317–318 CNLP (conditional nonlinear planning), 401 CNN (convolutional neural network), 811, 1003 co-NP, 1076 co-NP-complete, 240, 1076 coalition, 616 coalition structure, 616 coalition structure graph, 621 coarse-to-fine search, 126 Coase, R. H., 639, 1091 coastal navigation, 964 Coates

…

, 1094 Nowak, R., 473, 1090 Nowatzyk, A., 222, 1099 Nowick, S. M., 268, 1108 Nowlan, S. J., 136, 161, 1098 NP (hard problems), 1075–1076 NP-complete, 27, 124, 241, 266, 359, 452, 734, 1075, 1076 NP-hard, 1076 NQTHM (theorem prover), 330 number statement, 649 number variable, 650 NumPy, 738 NUPRL

The Golden Ticket: P, NP, and the Search for the Impossible

by Lance Fortnow · 30 Mar 2013 · 236pp · 50,763 words

benefits and unexpected challenges of the P-NP problem”—Provided by publisher. Includes bibliographical references and index. ISBN 978-0-691-15649-1 (hardback) 1. NP-complete problems. 2. Computer algorithms. I. Title. QA267.7.F67 2013 511.3’52—dc23 2012039523 British Library Cataloging-in-Publication Data is available This book

…

put out the fire as before. The mathematician responded, “I just reduced the problem to a previously solved case.” —Old math joke The First NP-Complete Problem Tom Hull, chair of the University of Toronto Computer Science Department in 1970, wanted to hire Steve Cook. Steve Cook had just been denied

…

bit more tongue-in-cheek, like “hard-boiled” (in honor of Cook) and “hard-ass” (“hard as satisfiability”). The winning write-in vote was for “NP-complete,” which was proposed by several people at Bell Labs in New Jersey after considerable discussion among the researchers there. The word “complete” comes from mathematical

…

logic, where a set of facts is complete if it can explain all the true statements in some logical system. Analogously, “NP-complete” means those problems in NP powerful enough that they can be used to solve any other problem in NP. Knuth was not entirely happy with

…

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,

…

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.

…

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. Large Sudoku Games Sudoku is a Japanese puzzle with numbers in a 9 × 9 grid as follows. Figure 4-2. Sudoku. The goal of

…

once? Now a computer search will start to take significant time, and 100 × 100 games can defeat today’s fastest machines. Large Sudoku games are NP-complete. Think you are good at Sudoku? If you can reliably solve large puzzles, then you can solve satisfiability, traveling salesman problems, and thousands of

…

other NP-complete problems. Sudoku is hardly the only NP-complete solitaire game. Consider the Minesweeper game built into Microsoft Windows. Figure 4-5. Minesweeper. Each number in a square tells how many

…

think there are bombs there. Click on a bomb and you lose the game. Determining whether one can win a large Minesweeper game is also NP-complete. Here are the remaining bombs in the above game. Figure 4-6. Minesweeper Bombs. Figure 4-7. Tetris. Then, of course, we have Tetris,

…

’t know what shape will come next. But even if you knew the order of shapes ahead of time, playing Tetris optimally is once again NP-complete. Who would think playing Sudoku, Minesweeper, or Tetris well would show P = NP and solve one of the biggest challenges of our generation? Figure

…

game of Minesweeper. The Ones That Got Away Most of the NP problems that people considered in the mid-1970s either turned out to be NP-complete or people found efficient algorithms putting them in P. But some NP problems refused to be so nicely and quickly characterized. Some would be

…

whether we have some algorithm that can always find a matching when one exists, is still unknown. Nor do we know if graph isomorphism is NP-complete and for various technical reasons, computer scientists don’t believe that it is. Graph isomorphism is one of the few problems whose difficulty seems somewhat

…

harder than P but not as hard as NP-complete problems like Hamiltonian paths and max-cut. Prime Numbers and Factoring You can break down (factor) the number 15 as 15 × 1 or 5

…

313,040,029,095,633,352,319,623. Computer scientists don’t believe that factoring is in P, nor do we believe that factoring is NP-complete. Factoring is a difficult problem, but maybe not as hard as satisfiability or map coloring. The importance of primes and factoring goes way beyond

…

in theory and practice. Not bad for a problem still considered unresolved into the late 1970s. * Computers and Intractability: A Guide to the Theory of NP-Completeness, by Michael Garey and David Johnson (New York: W. H. Freeman, 1979). Chapter 5 THE PREHISTORY OF P VERSUS NP One does not fear

…

, but rather uses it reasonably.* IN THE LAST CHAPTER WE RECOUNTED Donald Knuth’s ultimately unsuccessful attempt to find a good English word to capture NP-completeness. Knuth could have turned east to the Russians to find perebor (Перебор). Perebor means “brute force search,” the process of trying all possibilities to

…

mathematician, who measured complexity via algorithmic information. 3. Kolmogorov’s student Leonid Levin, who independently developed the P versus NP problem and the theory of NP-completeness but for political reasons couldn’t get a PhD in his native land. Sergey Yablonsky Research in computation in Russia went under the name theoretical

…

led Levin to think about problems that captured search, and he came up with the notion of “universal search problems,” equivalent to the notion of NP-completeness developed by Cook. Levin devised a list of six universal search problems, including the satisfiability problem, and formulated the P versus NP problem. Levin had

…

not share in Cook’s 1982 Turing Award, and it wasn’t until the late 1980s that people started consistently calling the first results on NP-completeness the Cook-Levin theorem. Relations between the Soviet Union and the United States started to open up in the 1980s. Alexander Razborov, a Russian

…

we have some non-Martian evidence. Researchers in Russia and North America with limited communication ended up developing the same P versus NP question and NP-complete problems. They had different motivation, in the East to understand the necessity of perebor and in the West to understand the power of efficient computation

…

-Phone. Does George create a beautiful algorithm that will always find the best possible schedule? No. But does George get the job done? Yes. NP-complete problems are nasty creatures, and if P ≠ NP we won’t find fast algorithms that always produce the best solution that works for all possible

…

then use 2009 technology than to solve your problem using 1971 technology. For some other NP problems we can do ever larger examples. The NP-complete traveling salesman problem tries to find the best way to visit a large number of cities using the shortest total distance. Using something called the

…

grow dramatically, with Moore’s law reflected in the greatly increasing number of core processors on a chip. This will help us solve even larger NP-complete problems in the future. But the complexity of the problem also increases greatly with the problem size. Don’t expect algorithms to solve all

…

always giving the right answer but finding solutions for most of the problems you want to solve. People have created heuristics for NP-complete problems well before we knew they were NP-complete. Over the decades, we have developed a number of sophisticated heuristic procedures for a variety of hard problems. None of these

…

procedures works on all instances for an NP-complete problem. But, depending on the context, many of these heuristic algorithms can solve the problems we need to solve. Let us analyze in detail

…

). If this heuristic always gives the right answer, then it gives us an efficient algorithm for map three-coloring, and since map three-coloring is NP-complete, we would have an efficient algorithm for all NP problems, and P = NP. So you should suspect at this point that the heuristic doesn

…

of six, 88 sextillion (88 followed by twenty-one zeros). Pretty quickly these numbers get well beyond what our machines can handle. For other NP-complete problems, searching for small solutions might be easier. A group in Frenemy is considered to be very cozy if for every two people who are

…

and Harry. Figure 6-10. Very Cozy Group Three. The very cozy problem, better known as “vertex cover,” is one of Karp’s original NP-complete problems. Look at Frank in the friendship diagram above. If Frank was not in a very cozy group, then the group must contain George, Danielle

…

about the same time as searching for cliques with three people. But wait! Didn’t Karp show that finding the smallest very cozy group is NP-complete? It doesn’t seem all that hard to find very cozy groups. Think about Frenemy and the vast friendship people have. It seems quite

…

be back in the black even though I never did find the absolute best route. Even though the traveling salesman problem on a map is NP-complete and presumably difficult to solve exactly, we can find tours that get very close to the best solution. Sanjeev Arora and Joe Mitchell give

…

problem where we have certain types of rules about how we can color neighboring countries. The unique games conjecture says the unique games problem is NP-complete. The jury is still out on whether or not the unique games conjecture is true. If the unique games conjecture is true, we can

…

can’t solve the problem we want to solve, so we try to solve a different problem. But even that different problem may still be NP-complete, so we try some heuristics to attack it. The heuristics rarely solve the problem, but they may give good enough approximate solutions. If P =

…

those messages using Alice’s public key and check that they match Alice’s original encryptions. As we mentioned back in chapter 4, Sudoku is NP-complete, so every NP problem can be reduced to Sudoku. So we automatically get a zero-knowledge system for every NP problem. Alice can convince

…

factors just by picking two large, randomly chosen prime numbers and multiplying them together. Factoring is not known or even believed to be NP-complete. Even if factoring were NP-complete, P ≠ NP just means there would be some numbers that are hard to factor. It could be the case that randomly chosen

…

numbers would still be easy to factor. Basing cryptography on NP-complete problems and on a P ≠ NP assumption remains a difficult challenge in cryptography. The change in cryptography started by Diffie and Hellman in the

…

take advantage of. While we think factoring is very difficult for today’s computers, a quantum computer could overcome these difficulties to factor large numbers. NP-complete problems lack a nice algebraic structure, which is why Shor’s algorithm won’t work to solve general NP problems. Of course, before we

…

quantum systems. They may help us break codes and help us better understand the fundamental nature of the universe, but they likely won’t solve NP-complete problems or make spreadsheets run faster. Quantum Cryptography Most of the cryptographic tools we discussed in chapter 8 are secure under the assumption that factoring

…

there. Future of Quantum Some researchers feel that we should rethink all of our computing in terms of quantum. Even if they don’t solve NP-complete problems, their ability to simulate the quantum world will lead to great new advances in our understanding of matter, the cosmos, and even the

…

a way to classify computational problems by their inherent difficulty. Even without a proof that P ≠ NP, when we find ourselves needing to solve an NP-complete problem, we know we won’t succeed in finding an algorithm that quickly solves the problem all the time. We need to rely on other

…

tools, a combination of approximation, heuristics, and computational firepower, simply to do the best we can. NP-completeness gives us a common framework and allows us to create a toolbox of techniques that we can throw at these difficult-to-compute problems. P

…

versus NP brings communities together. We have NP-complete problems in physics, biology, economics, and many other fields. Physicists and economists work on very different problems, but they share a commonality that can

…

blog. The province map of Frenemy is based on constructions in David P. Dailey, “Uniqueness of Colorability and Colorability of Planar 4-Regular Graphs Are NP-Complete,” Discrete Mathematics 30 (1980): 289–93. Chapter 7 The quotation from Juris Hartmanis in the first sentence is from a course he taught at Cornell

…

Minsk, 12 brain, in hand control, 5–6 Brassard, Gilles, 148, 150 A Brief History of Time (Hawking), x Brown, George, 26 brute force, for NP-complete problems, 90–92, 91 byte, size of, 2 Caesar cipher, 123, 123–24 Cambridge University, 73 cancer, curing, 14–15 Cardano, Gerolamo, 119–20 card

…

23–25 criminal profiling, 25–26 cryptography: Cardano and, 120; challenges in, 140–41; fully homomorphic, 138–39; history of, 123–26; modern, 126–29; NP-complete problems in, 140–41, 162; if P = NP, 129–30; quantum, 130, 148–49; randomness in, 140; zero-knowledge proofs and, 135–36 cutting-plane

…

, 116; in economics, 49; examples of, 46; in mathematics, 49–50; meaning of, ix, 4; in physics, 48, 48; reduction to satisfiability, 54–55 NP-complete problems: accepting unsolvability of, 107–8; approximation for, 99–104, 100, 101, 102, 103; brute force approach to, 90–92, 91; categorizing, 59; changing the

…

imagined possibilities of, 12–19, 23–27; implications of, ix, 6, 9, 10, 46; importance of question, 46; likelihood of, 9, 28; meaning of, 4; NP-complete problems and, 59; proving, versus P ≠ NP, 120–21; random number generation and, 140; as satisfiability, 54–55; very cozy groups and, 104 P ≠ NP

The Road to Conscious Machines

by Michael Wooldridge · 2 Nov 2018 · 346pp · 97,890 words

going to be feasible for most cases of interest. The reason for this is that our problem is an example of what is called an NP-complete problem. I’m afraid the acronym is not helpful for the uninitiated: ‘NP’ stands for ‘non-deterministic polynomial time’, and the technical meaning is rather

…

complex. Fortunately, the intuition behind NP-complete problems is simple. An NP-complete problem is a combinatorial problem, like our team-building example, in which it is hard to find solutions (because there are too many

…

example, we can check a possible solution by simply verifying that it doesn’t contain any forbidden pairings). There is one other important characteristic of NP-complete problems. To understand it, we need to introduce another problem (trust me, I’m doing this for a good reason). Our next problem is rather

…

all, what does team building have to do with finding the shortest tour in a road network? But now comes the really remarkable thing about NP-complete problems: although they appear to be completely different, they are, ultimately, the same problem. To see what I mean by this, imagine I had ingeniously

…

a quick technique to solve the travelling salesman problem. And this doesn’t hold for just these two problems: the same is true for all NP-complete problems. All NP-complete problems have this property: they can all easily be transformed into each other. This remarkable result means that all

…

NP-complete problems stand or fall together. If you could find a quick recipe for solving just one NP-complete problem, then you would also have found a quick recipe for solving all of them. But, to

…

date, nobody has found an efficient recipe for any NP-complete problem. And the question of whether NP-complete problems can be efficiently solved is, in fact, one of the most important open problems in science today. It is known as

…

dollars from the Clay Mathematics Institute, who in the year 2000 identified it as one of the ‘Millennium Problems’ in mathematics. Smart money says that NP-complete problems cannot be solved efficiently; but smart money also says that we are a long way from knowing for certain whether this really is the

…

case. If you discover that a problem you are working on is NP-complete, then this tells you that conventional techniques to solve it are just not going to work: your problem is, in a precise mathematical sense, hard

…

. The basic structure of NP-complete problems was unravelled in a series of articles in the early 1970s: a 1971 paper by American-Canadian mathematician Stephen Cook established the central idea

…

, and a subsequent paper by American Richard Karp demonstrated that the range of Cook’s NP-complete problems was much wider than was first thought. Throughout the 1970s, researchers in AI started to look at the problems that they had been working

…

on using the theory of NP-completeness. And the results were shocking. Everywhere they looked – in problem solving, game playing, planning, learning, reasoning – it seemed that key problems were

…

NP-complete (or worse). The phenomenon was so ubiquitous that it became a joke – the term ‘AI-complete’ came to mean ‘a problem as hard as AI

…

-complete problem, so the joke went, you would solve them all. Discovering that the problems you were working on were NP-complete – or worse – was a heavy blow. Before the theory of NP-completeness and its consequences were understood, there was always a hope that some sudden breakthrough would render these problems easy – tractable

…

technical term. And technically, such a hope still remains, since we don’t yet know for certain that NP-complete problems cannot be solved efficiently. But by the late 1970s the spectre of NP-completeness and combinatorial explosion began to loom large over the AI landscape. The field had hit a barrier, in the

…

for computers to solve. Back then, there had always been the possibility that some breakthrough would render the difficult problems easy. But when understanding of NP-completeness began to spread, the community began to understand what it really meant for a computational problem to be hard. The End of the Golden Age

…

major achievement of the time, although its ramifications are probably more profound. You may recall from Chapter 2 that certain computational problems are intrinsically hard – NP-complete, to use the technical term – and that many problems of interest in AI fall into this category. By the early 1990s, it was beginning to

…

be clear that progress on algorithms for NP-complete problems was such that this no longer represented the fundamental barrier that it had appeared two decades before.19 The first problem shown to be

…

NP-complete was called SAT (short for ‘satisfiability’). This is the problem of checking whether simple logical expressions are consistent – whether there is any way they could

…

be true. SAT is the most fundamental of all NP-complete problems, and you will recall that, if you have an efficient way to solve just one type of NP-complete problem, then you have automatically found a way to solve them all. By the end of

…

so efficient that they are now routinely used throughout computing – they are just another tool that we call on when faced with NP-complete problems. This doesn’t mean that NP-complete problems can now always be solved efficiently: there will always be cases that bring even the best SAT solvers to their knees

…

. But we are no longer afraid of NP-completeness, and this is one of the major unsung achievements of AI over the past four decades. For all its newfound respectability, not everyone was happy

…

with them via an axon. The basic information-processing unit of the brain, and the inspiration for neural nets. NP-complete A class of computational problems that resist attempts to solve them efficiently. The theory of NP-completeness was developed in the 1970s, and in this time many AI problems were discovered to be

…

NP-complete. See also P vs NP problem. ontological engineering In an expert system (and, more generally, in a knowledge-based system

…

what those weights ‘mean’. This means that current neural nets can’t explain or justify their decisions. P vs NP problem The question of whether NP-complete problems definitely can or cannot always be solved efficiently. One of the biggest open problems in mathematics today. Not likely to be settled any time

…

responsible for reacting, planning and modelling respectively. tractable problem A problem is said to be tractable if we have an efficient algorithm to solve it. NP-complete problems are not tractable: we don’t have algorithms that are guaranteed to solve them efficiently. See also P vs NP problem. training (in machine

…

’ – a feasible algorithm to solve a problem is one that has ‘polynomial running time’. See the Further Reading section for pointers to the literature on NP-completeness and the P vs NP problem. * * * CHAPTER 3: KNOWLEDGE IS POWER 1. P. Winston and B. Horn. LISP (3rd edn). Pearson, 1989. 2. E. H

…

–2 natural languages 56 negative feedback 173 neural nets/neural networks 44, 168, 173–90, 369–72 neurons 174 Newell, Alan 52–3 norms 260 NP-complete problems 81–5, 164–5 nuclear energy 242–3 nuclear fusion 305 O ontological engineering 117 Osborne, Michael 268–70 P P vs NP problem

Algorithms in C++ Part 5: Graph Algorithms

by Robert Sedgewick · 2 Jan 1992

with edge weights that could be negative (see Section 21.7), which is simple to solve in linear time if there are no cycles but NP-complete if cycles are allowed. But the maxflow problem, remarkably, is no easier for acyclic networks. Property 22.16 The maxflow problem for acyclic networks is

…

., “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proceedings AMS, 7, 1 (1956). K. Mehlhorn, Data Structures and Algorithms 2:NP-Completeness and Graph Algorithms, Springer-Verlag, 1984. C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982. R. C. Prim, “Shortest connection

The Art of Computer Programming

by Donald Ervin Knuth · 15 Jan 2001

in SICOMP 9 A980), 713-728. However, the problem of computing the tensor rank of an arbitrary nxnx n tensor over any finite field is NP-complete [J. Hastad, Journal of Algorithms 11 A990), 644-654]. 4.6.4 EVALUATION OF POLYNOMIALS 515 For further reading. In this section we have barely

…

a minimum vertex cover is NP-hard (see Section 7.9), the problem of computing l(ni,..., nm) is NP-complete. [It is unknown whether or not the problem of computing l(n) is NP- complete. But it seems plausible that an optimum chain for, say, X^fcTcI ^fc+i2Afe2 would entail an optimum

…

, 29. Norton, Graham Hilton, 372, 673. Norton, Karl Kenneth, 383. Norton, Victor Thane, Jr., 607. Notations, index to, 730-734. Nozaki, Akihiro (ff*§Hg3A), 524. NP-complete problems, 499, 514, 585, 698. Null space of a matrix, 443-444, 456, 659-660, 681. Number field sieve, 403. Number fields, 331, 333, 345

Applied Cryptography: Protocols, Algorithms, and Source Code in C

by Bruce Schneier · 10 Nov 1993

are called isomorphic. For an extremely large graph, finding whether two graphs are isomorphic can take centuries of computer time; it’s one of those NP-complete problems discussed in Section 11.1. Assume that Peggy knows the isomorphism between the two graphs, G1 and G2. The following protocol will convince Victor

…

proved my own foolishness by making predictions. DNA Computing Now it gets weird. In 1994 Leonard M. Adleman actually demonstrated a method for solving an NP-complete problem (see Section 11.2) in a biochemistry laboratory, using DNA molecules to represent guesses at solutions to the problem [17]. (That’s “solutions” meaning

…

that it represents: This is the solution to the directed Hamiltonian path problem. By definition, an instance of any NP-complete problem can be transformed, in polynomial time, into an instance of any other NP-complete problem, and therefore into an instance of the directed Hamiltonian path problem. Since the 1970s, cryptologists have been

…

trying to use NP-complete problems for public-key cryptography. While the instance that Adleman solved was very modest (seven cities on his map, a problem that can be solved

…

its infancy and has no forbidding obstacles keeping it from being extended to larger problems. Thus, arguments about the security of cryptographic protocols based on NP-complete problems, arguments that heretofore have begun, “Suppose an adversary has a million processors, each of which can perform a million tests each second,” may soon

…

the Satisfiability problem (given a propositional Boolean formula, is there a way to assign truth values to the variables that makes the formula true?) is NP-complete . This means that, if Satisfiability is solvable in polynomial time, then P = NP. Conversely, if any problem in NP can be proven not to have

…

been shown to be equivalent to Satisfiability; hundreds are listed in [600], and some examples follow. By equivalent, I mean that these problems are also NP-complete; they are in NP and also as hard as any problem in NP . If their solvability in deterministic polynomial time were resolved, the P versus

…

(s): Bruce Schneier ISBN: 0471128457 Publication Date: 01/01/96 Search this book: Go! Previous Table of Contents Next ----------- NP-Complete Problems Michael Garey and David Johnson compiled a list of over 300 NP-complete problems [600]. Here are just a few of them: — Traveling Salesman Problem. A traveling salesman has to visit n

…

system for digital signatures [1413]. Knapsack algorithms get their security from the knapsack problem, an NP-complete problem. Although this algorithm was later found to be insecure, it is worth examining because it demonstrates how an NP-complete problem can be used for public-key cryptography. The knapsack problem is a simple one. Given

…

fast algorithm for decoding Goppa codes, but the general problem of finding a code word of a given weight in a linear binary code is NP-complete. A good description of this algorithm can be found in [1233]; see also [1562]. Following is just a quick summary. Let dH(x,y) denote

…

Nonce-verification rule, 66 Non-Interactive Key Sharing systems, 115 Nonlinear-feedback shift registers, 412–413 Nonlinear keyspace, 175–176 Nonrepudiation, 2 Notz, Bill, 266 NP-complete problem, 240–242 graph isomorphism, 104 knapsack algorithms, 462 McEliece algorithm, 479 solving, 163–164 NRL Protocol Analyzer, 67–68 NSDD-145, 268 Nuclear Non

…

, 184 Probabilistic encryption, 552–554 Problems: complexity, 239–241 EXPTIME, 241 hard, 239 intractable, 239 PSPACE, 241 Problems (Cont.) tractable, 239 undecidable, 240 See also NP-complete problem Processing complexity, 9 Product cipher, 347 Proofs of Membership, 111 Propagating cipher block chaining mode, 207 Proposed Encryption Standard, 319 Protocols, 21, 47 adjudicated

Algorithms Unlocked

by Thomas H. Cormen · 15 Jan 2013

168 Further reading 178 Contents 10 vii Hard? Problems 179 Brown trucks 179 The classes P and NP and NP-completeness Decision problems and reductions 185 A Mother Problem 188 A sampler of NP-complete problems 190 General strategies 205 Perspective 208 Undecidable problems 210 Wrap-up 211 Further reading 212 Bibliography Index 215

…

c is a constant, then there would be an algorithm that ran in O.nc / time for all of these problems. We call these problems NP-complete. An algorithm that runs in time O.nc / on an input of size n, where c is a constant, is a polynomial-time algorithm, so

…

in the running time. We know of no polynomial-time algorithm for any NP-complete problem, but nobody has proven that it’s impossible to solve some NP-complete problem in polynomial time. And there’s even more frustration: many NP-complete problems are almost the same as problems that we know how to solve in

…

easy. You might be surprised to learn, however, that finding a longest acyclic path (that is, a longest path without cycles) between two vertices is NP-complete. In fact, merely determining whether a graph contains a path without cycles with at least a given number of edges is

…

NP-complete. As another example of related problems, where one is easy and one is NP-complete, consider Euler tours and hamiltonian cycles. Both of these problems have to do with finding paths in a

…

and only if the degree of every vertex is even. But if we ask whether a connected, undirected graph has a hamiltonian cycle, that’s NP-complete. Notice that the question is not “what is the order of vertices on a hamiltonian cycle in this graph?” but just the more basic “yes

…

or no: is it possible to construct a hamiltonian cycle on this graph?” NP-complete problems come up surprisingly often, which is why I’m including material on them in this book. If you are trying to find a polynomial

…

NPcomplete, you are likely to be in for a big helping of disappointment. (But see the section on perspective, pages 208–211.) The concept of NP-complete problems has been around since the early 1970s, and people were trying to solve problems that turned out to be

…

NP-complete (such as the traveling-salesman problem) well before then. To date, we 2 So named because the mathematician Leonhard Euler proved in 1736 that it

…

without resolving it. I’m not saying that you cannot find a polynomialtime algorithm for an NP-complete problem, but you would be facing long odds if you were to try. The classes P and NP and NP-completeness In the previous chapters, I was concerned about differences in running times such as O

…

question that has perplexed computer scientists for all these years. We often call it the “P D NP‹ problem.” The NP-complete problems are the “hardest” in NP. Informally, a problem is NP-complete if it satisfies two conditions: (1) it’s in NP and (2) if a polynomial-time algorithm exists for the

…

a way as to solve them all in polynomial time. If a polynomial-time algorithm exists for any NP-complete problem—that is, if any NP-complete problem is in P—then P D NP. Because NP-complete problems are the hardest in NP, if it turns out that any problem in NP is not polynomial

…

-time solvable, then none of the NP-complete problems are. A problem is NP-hard if it satisfies the second condition for NP-completeness but may or may not be in NP. Here’s a handy list of the pertinent definitions: P

…

problem, then we can convert every problem in NP into this problem in such a way to solve every problem in NP in polynomial time. NP-complete: a problem that is NP-hard and also in NP. 4 You probably surmised that the name P comes from “polynomial time.” If you’re

…

a shortest path contains, but at least it will tell us the weight of a shortest path. The second condition for a problem to be NP-complete requires that if a polynomial-time algorithm exists for the problem, then there is a way to convert every problem in NP into this problem

…

that it also reduces to Y in polynomial time. Our ultimate goal is to show that problems are NP-complete. So now all we have to do to show that a problem Y is NP-complete is show that it’s in NP, which we can do by showing that there’s a way

…

from X to Y. There is one more little detail that I’ve ignored so far: the Mother Problem. We need to start with some NP-complete problem M (the Mother Problem) that every problem in NP reduces to in polynomial time. Then we can reduce M to some other problem in

…

mind, too, that there’s no limit on how many other problems we can reduce a single problem to, so that the family tree of NP-complete problems starts with the Mother Problem and then branches out. A Mother Problem Different books list different Mother Problems. That’s fine, since once you

…

AND 1, which is 0; if instead x D 1, then this formula evaluates to 1 AND 0, which again is 0. A sampler of NP-complete problems With boolean formula satisfiability as our Mother Problem, let’s see some of the problems that we can show are

…

NP-complete by using polynomial-time reductions. Here’s the family tree of reductions that we’ll see: Mother Problem: boolean formula satisfiability 3-CNF satisfiability clique

…

to NOT y from clause Ci and ´ from clauses C2 and C3 . Thus, we have shown that there exists a polynomial-time reduction from the NP-complete problem of 3-CNF satisfiability to the problem of finding a k-clique. If you were given a boolean formula in 3-CNF with k

…

a k-clique, then you would have determined in polynomial time whether the 3-CNF formula had a satisfying assignment. Since 3-CNF satisfiability is NP-complete, so is determining whether a graph contains a k-clique. As a bonus, if you could determine not only whether the graph had a k

…

the proposed vertex cover has size m and really does cover all the edges, and so we see that this problem is in NP. The NP-completeness family tree on page 190 tells you that we reduce the clique problem to the vertex-cover problem. Suppose that the input to the clique

…

pairs of vertices in C . That is, C is a k-clique. Thus, we have shown that there exists a polynomial-time reduction from the NP-complete problem of determining whether an undirected graph contains a k-clique to the problem of determining whether an undirected graph contains a vertex cover of

…

vertex cover of size n k, then you would have determined in polynomial time whether G had a k-clique. Since the clique problem is NP-complete, so is the vertex-cover problem. As a bonus, if you could determine not only whether G had a vertex cover of n k vertices

…

and ends at the same vertex and visits all other vertices exactly once)? The applications of this problem are a bit arcane, but from the NP-completeness family tree on page 190, you can see that we use this problem to show that the traveling-salesman problem is

…

NP-complete, and we’ve seen how the traveling-salesman problem comes up in practice. A closely related problem is the hamiltonian-path problem, which asks whether

…

once, but does not require that the path be a closed cycle. This problem, too, is NP-complete, and we will use it on page 199 to show that the longest-acyclic-path problem is NP-complete. For both of the hamiltonian problems, the certificate is obvious: the order of the vertices in the

…

G 0 , along with .vi ; u/. A similar denouement to those of our previous reductions holds here. There exists a polynomial-time reduction from the NP-complete problem of determining whether a connected, undirected graph contains a hamiltonian cycle to the problem of determining whether a connected, undirected graph contains a hamiltonian

…

adding up the numbers in the subset and checking that their sum equals t. 200 Chapter 10: Hard? Problems As you can see from the NP-completeness family tree on page 190, we show that the subset-sum problem is NP-hard by reducing from 3-CNF satisfiability. Here is another reduction

…

subset-sum problem in polynomial time, we could also determine whether a 3-CNF formula is satisfiable in polynomial time. Since 3-CNF satisfiability is NP-complete, so is the subset-sum problem. Moreover, if we know which integers in the constructed set S sum to the target t, we can determine

…

hard as the partition problem, and we don’t even need to go through the full reduction process to show that the knapsack problem is NP-complete. General strategies As you have probably realized by now, there is no one-size-fits-all way to reduce one problem to another in order

…

it. The hamiltonian-cycle problem is more restricted because each edge has only one of two “values”: present or absent. Look for special cases Several NP-complete problems are just special cases of other NPcomplete problems, much as the partition problem is a special case of Chapter 10: Hard? Problems 207 the

…

knapsack problem. If you know that problem X is NP-complete and that it’s a special case of problem Y, then problem Y must be NPcomplete as well. That is because, as we saw for

…

you’re trying to prove NPcomplete. For example, we showed that the vertex-cover problem—a graph problem—was NP-complete by reducing from the clique problem—also a graph problem. From there, the NP-completeness family tree showed that we reduced to the hamiltonian-cycle, hamiltonian-path, traveling-salesman, and longest-acyclic-path

…

. Eventually you suspect that maybe—just maybe—you’ve been banging your head against the wall to solve an NP-complete problem. And, lo and behold, you are able to reduce a known NP-complete problem to your problem, and now you know that it’s NP-hard. Is that the end of the

…

? There’s no hope that you’ll be able to solve the problem in any reasonable amount of time? Not quite. When a problem is NP-complete, it means that some inputs are troublesome, but not necessarily that all inputs are bad. For example, finding a longest acyclic path in a directed

…

graph is NP-complete, but if you know that the graph is acyclic, then you can find a longest acyclic path in not just polynomial time, but in O

…

have equal sums. The good news goes beyond such pathological special cases. From here on, let’s focus on optimization problems whose decision variants are NP-complete, such as the traveling-salesman problem. Some fast methods give good, and often very good, results. The technique of branch and bound organizes a search

…

are points in the plane and the weight of each edge is the planar distance between the points. Even with this restriction, the problem is NP-complete. In the 2-opt technique, whenever two edges cross, switch them, which results in a shorter cycle: Moreover, a host of approximation algorithms give results

…

polynomial-time approximation algorithm for this situation, giving a tour whose total weight is at most 3=2 times the lowest. Strangely enough, if two NP-complete problems are closely related, the solution produced by a good approximation algorithm for one might produce a poor solution for the other. That is, a

…

save by planning efficient routes helps their bottom line. 210 Chapter 10: Hard? Problems Undecidable problems Then again, if you’re under the impression that NP-complete problems are the hardest in the world of algorithms, you’re in for a little surprise. Theoretical computer scientists have defined a large hierarchy of

…

as questions yet to be asked. Take an algorithms course—you can even take one online—and help us out! Further reading The book on NP-completeness is by Garey and Johnson [GJ79]. If you’re interested in delving into this topic, read it. CLRS [CLRS09] has a chapter on

…

NP-completeness, which goes into more technical detail than I’ve gone into here, and it also has a chapter on approximation algorithms. For more on computability

…

/fips/fips140-2/fips1402annexc.pdf, July 2011. Draft. [GJ79] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. [Gri81] David Gries. The Science of Programming. Springer, 1981. [KL08] Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. Chapman & Hall

…

by Bellman-Ford algorithm, 103–104 neighborhood search, 209 219 nested loops, 34 network communication, 4 node, 98 internal, 162 NOR, 189 NP, 184 NP-complete, 181, 184 NP-completeness of clique, 191–194 general strategies for proving, 205–208 of hamiltonian cycle, 196–198 of hamiltonian path, 196–198 of knapsack, 205 of

Algorithms to Live By: The Computer Science of Human Decisions

by Brian Christian and Tom Griffiths · 4 Apr 2016 · 523pp · 143,139 words

scheduling problems that Eugene Lawler encountered in chapter 5 fall into this category. An NP-hard problem that is itself in NP is known as “NP-complete.” See Karp, “Reducibility Among Combinatorial Problems,” for the classic result showing that a version of the traveling salesman problem is

…

NP-complete, and Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, for an accessible introduction to P and NP. most computer scientists believe

…

only nine thought P = NP (Gasarch, “The P =? NP Poll”). While proving P = NP could be done by exhibiting a polynomial-time algorithm for an NP-complete problem, proving P ≠ NP requires making complex arguments about the limits of polynomial-time algorithms, and there wasn’t much agreement among the people surveyed

…

,” where twenty-one problems were famously shown to be in this set. By the end of the 1970s, computer scientists had identified some three hundred NP-complete problems (Garey and Johnson, Computers and Intractability), and the list has grown significantly since then. These include some problems that are very familiar to humans

…

. In 2003, Sudoku was shown to be NP-complete (Yato and Seta, “Complexity and Completeness”), as was maximizing the number of cleared rows in Tetris, even with perfect knowledge of future pieces (Demaine, Hohenberger

…

the class could also be solved efficiently (including making the world’s neatest sandwiches). But being PPAD-complete is not quite so bad as being NP-complete. P, the class of efficiently solvable problems, could be equal to PPAD without being equal to NP. As of this writing the jury is still

…

Nash, “The Bargaining Problem.” minimize the number of coins: Shallit, “What This Country Needs Is an 18¢ Piece.” ungainly denominations turn change-making: Lueker, “Two NP-Complete Problems in Nonnegative Integer Programming,” showed that under certain assumptions, making change with the fewest number of coins is NP-hard. This result holds if

…

, P., and C. Kerry. Digital Signature Standard. FIPS PUB 186-4, 2013. Garey, Michael R., and David S. Johnson. Computers and Intractability: A Guide to NP-Completeness. New York: W. H. Freeman, 1979. Garfield, Eugene. “Recognizing the Role of Chance.” Scientist 2, no. 8 (1988): 10. Garrett, A. J. M., and P

…

Model of Happiness: Reactions to Changes in Marital Status.” Journal of Personality and Social Psychology 84, no. 3 (2003): 527–539. Lueker, George S. “Two NP-Complete Problems in Nonnegative Integer Programming.” Technical Report TR-178, Computer Science Laboratory, Princeton University, 1975. Luria, Salvador E. A Slot Machine, a Broken Test Tube

Silence on the Wire: A Field Guide to Passive Reconnaissance and Indirect Attacks

by Michal Zalewski · 4 Apr 2005 · 412pp · 104,864 words

a computer: much of today’s cryptography is based on the relative difficulty of solving a set of so-called non-polynomial[33] (NP) problems. NP-complete problems seem to take pleasure in crashing every codebreaker’s party at the least opportune times. The ability to solve them efficiently—whether with enormous

Hands-On Machine Learning With Scikit-Learn and TensorFlow: Concepts, Tools, and Techniques to Build Intelligent Systems

by Aurélien Géron · 13 Mar 2017 · 1,331pp · 163,200 words

produces a reasonably good solution, but it is not guaranteed to be the optimal solution. Unfortunately, finding the optimal tree is known to be an NP-Complete problem:2 it requires O(exp(m)) time, making the problem intractable even for fairly small training sets. This is why we must settle for

…

can be verified in polynomial time. An NP-Hard problem is a problem to which any NP problem can be reduced in polynomial time. An NP-Complete problem is both NP and NP-Hard. A major open mathematical question is whether or not P = NP. If P ≠ NP (which seems likely), then

…

no polynomial algorithm will ever be found for any NP-Complete problem (except perhaps on a quantum computer). 3 log2 is the binary logarithm. It is equal to log2(m) = log(m) / log(2). 4 A

…

Normal Equation-Computational Complexity normalization, Feature Scaling normalized exponential, Softmax Regression norms, Select a Performance Measure notations, Select a Performance Measure-Select a Performance Measure NP-Complete problems, The CART Training Algorithm null hypothesis, Regularization Hyperparameters numerical differentiation, Numerical Differentiation NumPy, Create the Workspace NumPy arrays, Handling Text and Categorical Attributes NVidia