NP-complete

32 results back to index

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

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Andrew Wiles, Claude Shannon: information theory, cloud computing, complexity theory, Donald Knuth, Erdős number, four colour theorem, Gerolamo Cardano, Isaac Newton, James Webb Space Telescope, Johannes Kepler, John von Neumann, Large Hadron Collider, linear programming, new economy, NP-complete, Occam's razor, P = NP, Paul Erdős, quantum cryptography, quantum entanglement, Richard Feynman, Rubik’s Cube, seminal paper, smart grid, Stephen Hawking, traveling salesman, Turing machine, Turing test, Watson beat the top human players on Jeopardy!, William of Occam

A classic 1979 book* lists over three hundred major NP-complete problems. NP-complete problems continually arise in computer science, physics, biology, economics, and many other areas that reach that pinnacle of hardness. A Google Scholar search on “NP-Complete” returns over 138,000 scientific articles from 1972 to 2011, nearly 10,000 in 2011 alone. We can’t list all of them here, but let me give you a flavor of some of them. Dominating Set Are there fifty people in Frenemy such that everyone else is friends with at least one of them? NP-complete. Partition into Triangles The dorm rooms of the Frenemy Institute can each hold three students.

…

He truly wanted a single English world that captured the intuitive meaning of hard search problems, a term for the masses. In a 1974 wrap-up of his survey, Knuth wrote “NP-complete actually smacks of being a little too technical for a mass audience, but it’s not so bad as to be unusable.” “NP-complete” quickly became the standard terminology. It took Donald Knuth about four decades to finish volume 4. Knuth should have pushed a bit harder for less technical names for “NP-complete,” and perhaps for “P” and “NP” as well. The P versus NP problem has taken on an importance that goes well beyond computer science, and using terminology that just abbreviates a technical definition hides this import from outsiders.

…

Knuth also realized that all this fuss to come up with a name would be wasted if in fact P = NP, since then the NP-complete problems would be just the ones in P. But Knuth was “willing to risk such an embarrassment, and in fact I’m willing to give a prize of one live turkey to the first person who proves that P = NP.” So prove P = NP and you will win a million dollars and a turkey. Beyond Karp After Karp’s paper, an industry in computer science arose showing the NP-completeness of a large variety of search problems. Over the next several years, many professors and grad students took a number of known search problems (as well as some new ones) and showed them to be NP-complete. A classic 1979 book* lists over three hundred major NP-complete problems.

Algorithms Unlocked by Thomas H. Cormen

bioinformatics, Donald Knuth, knapsack problem, NP-complete, optical character recognition, P = NP, Silicon Valley, sorting algorithm, traveling salesman

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 problem, then there is a way to convert every problem in NP into this problem in such 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.

…

To take the frustration to a whole new level, here’s the most amazing fact: if there were an algorithm that ran in O.nc / time for any of these problems, where 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 called because nc with some coefficient would be the most significant term 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 polynomial time.

…

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 story? 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.n C m/ time (where the graph has n vertices and m edges).

The Road to Conscious Machines by Michael Wooldridge

Ada Lovelace, AI winter, algorithmic bias, AlphaGo, Andrew Wiles, Anthropocene, artificial general intelligence, Asilomar, augmented reality, autonomous vehicles, backpropagation, basic income, Bletchley Park, Boeing 747, British Empire, call centre, Charles Babbage, combinatorial explosion, computer vision, Computing Machinery and Intelligence, DARPA: Urban Challenge, deep learning, deepfake, DeepMind, Demis Hassabis, don't be evil, Donald Trump, driverless car, Elaine Herzberg, Elon Musk, Eratosthenes, factory automation, fake news, future of work, gamification, general purpose technology, Geoffrey Hinton, gig economy, Google Glasses, intangible asset, James Watt: steam engine, job automation, John von Neumann, Loebner Prize, Minecraft, Mustafa Suleyman, Nash equilibrium, Nick Bostrom, Norbert Wiener, NP-complete, P = NP, P vs NP, paperclip maximiser, pattern recognition, Philippa Foot, RAND corporation, Ray Kurzweil, Rodney Brooks, self-driving car, Silicon Valley, Stephen Hawking, Steven Pinker, strong AI, technological singularity, telemarketer, Tesla Model S, The Coming Technological Singularity, The Future of Employment, the scientific method, theory of mind, Thomas Bayes, Thomas Kuhn: the structure of scientific revolutions, traveling salesman, trolley problem, Turing machine, Turing test, universal basic income, Von Neumann architecture, warehouse robotics

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.

…

The phenomenon was so ubiquitous that it became a joke – the term ‘AI-complete’ came to mean ‘a problem as hard as AI itself’ – if you could solve one 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, to use the 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 form of computational complexity, and progress ground to a halt.

…

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.

The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World by Pedro Domingos

Albert Einstein, Amazon Mechanical Turk, Arthur Eddington, backpropagation, basic income, Bayesian statistics, Benoit Mandelbrot, bioinformatics, Black Swan, Brownian motion, cellular automata, Charles Babbage, Claude Shannon: information theory, combinatorial explosion, computer vision, constrained optimization, correlation does not imply causation, creative destruction, crowdsourcing, Danny Hillis, data is not the new oil, data is the new oil, data science, deep learning, DeepMind, double helix, Douglas Hofstadter, driverless car, Erik Brynjolfsson, experimental subject, Filter Bubble, future of work, Geoffrey Hinton, global village, Google Glasses, Gödel, Escher, Bach, Hans Moravec, incognito mode, information retrieval, Jeff Hawkins, job automation, John Markoff, John Snow's cholera map, John von Neumann, Joseph Schumpeter, Kevin Kelly, large language model, lone genius, machine translation, mandelbrot fractal, Mark Zuckerberg, Moneyball by Michael Lewis explains big data, Narrative Science, Nate Silver, natural language processing, Netflix Prize, Network effects, Nick Bostrom, NP-complete, off grid, P = NP, PageRank, pattern recognition, phenotype, planetary scale, power law, pre–internet, random walk, Ray Kurzweil, recommendation engine, Richard Feynman, scientific worldview, Second Machine Age, self-driving car, Silicon Valley, social intelligence, speech recognition, Stanford marshmallow experiment, statistical model, Stephen Hawking, Steven Levy, Steven Pinker, superintelligent machines, the long tail, the scientific method, The Signal and the Noise by Nate Silver, theory of mind, Thomas Bayes, transaction costs, Turing machine, Turing test, Vernor Vinge, Watson beat the top human players on Jeopardy!, white flight, yottabyte, zero-sum game

Humans are good at solving NP problems approximately, and conversely, problems that we find interesting (like Tetris) often have an “NP-ness” about them. One definition of artificial intelligence is that it consists of finding heuristic solutions to NP-complete problems. Often, we do this by reducing them to satisfiability, the canonical NP-complete problem: Can a given logical formula ever be true, or is it self-contradictory? If we invent a learner that can learn to solve satisfiability, it has a good claim to being the Master Algorithm. NP-completeness aside, the sheer existence of computers is itself a powerful sign that there is a Master Algorithm. If you could travel back in time to the early twentieth century and tell people that a soon-to-be-invented machine would solve problems in every realm of human endeavor—the same machine for every problem—no one would believe you.

…

(The names are not very mnemonic, unfortunately.) A problem is in P if we can solve it efficiently, and it’s in NP if we can efficiently check its solution. The famous P = NP question is whether every efficiently checkable problem is also efficiently solvable. Because of NP-completeness, all it takes to answer it is to prove that one NP-complete problem is efficiently solvable (or not). NP is not the hardest class of problems in computer science, but it’s arguably the hardest “realistic” class: if you can’t even check a problem’s solution before the universe ends, what’s the point of trying to solve it? Humans are good at solving NP problems approximately, and conversely, problems that we find interesting (like Tetris) often have an “NP-ness” about them.

…

The argument from computer science When I was a senior in college, I wasted a summer playing Tetris, a highly addictive video game where variously shaped pieces fall from above and which you try to pack as closely together as you can; the game is over when the pile of pieces reaches the top of the screen. Little did I know that this was my introduction to NP-completeness, the most important problem in theoretical computer science. Turns out that, far from an idle pursuit, mastering Tetris—really mastering it—is one of the most useful things you could ever do. If you can solve Tetris, you can solve thousands of the hardest and most important problems in science, technology, and management—all in one fell swoop.

Algorithms to Live By: The Computer Science of Human Decisions by Brian Christian, Tom Griffiths

4chan, Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, algorithmic bias, algorithmic trading, anthropic principle, asset allocation, autonomous vehicles, Bayesian statistics, behavioural economics, Berlin Wall, Big Tech, Bill Duvall, bitcoin, Boeing 747, Charles Babbage, cognitive load, Community Supported Agriculture, complexity theory, constrained optimization, cosmological principle, cryptocurrency, Danny Hillis, data science, David Heinemeier Hansson, David Sedaris, delayed gratification, dematerialisation, diversification, Donald Knuth, Donald Shoup, double helix, Dutch auction, Elon Musk, exponential backoff, fault tolerance, Fellow of the Royal Society, Firefox, first-price auction, Flash crash, Frederick Winslow Taylor, fulfillment center, Garrett Hardin, Geoffrey Hinton, George Akerlof, global supply chain, Google Chrome, heat death of the universe, Henri Poincaré, information retrieval, Internet Archive, Jeff Bezos, Johannes Kepler, John Nash: game theory, John von Neumann, Kickstarter, knapsack problem, Lao Tzu, Leonard Kleinrock, level 1 cache, linear programming, martingale, multi-armed bandit, Nash equilibrium, natural language processing, NP-complete, P = NP, packet switching, Pierre-Simon Laplace, power law, prediction markets, race to the bottom, RAND corporation, RFC: Request For Comment, Robert X Cringely, Sam Altman, scientific management, sealed-bid auction, second-price auction, self-driving car, Silicon Valley, Skype, sorting algorithm, spectrum auction, Stanford marshmallow experiment, Steve Jobs, stochastic process, Thomas Bayes, Thomas Malthus, Tragedy of the Commons, traveling salesman, Turing machine, urban planning, Vickrey auction, Vilfredo Pareto, Walter Mischel, Y Combinator, zero-sum game

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 that there aren’t any: In a 2002 survey of one hundred leading theoretical computer scientists, sixty-one thought P ≠ NP and 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 about exactly what kind of mathematics will be needed to solve this problem.

…

What’s more, many other optimization problems: This includes versions of vertex cover and set cover—two problems identified as belonging to NP in Karp, “Reducibility Among Combinatorial Problems,” 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, and Liben-Nowell, “Tetris Is Hard, Even to Approximate”).

…

(With n = 3, this involves figuring out the path a knife would have to travel to cut three sets of points in half; if those sets of points correspond to two pieces of bread and a piece of ham, the result is a perfectly bisected sandwich.) Finding Nash equilibria is actually PPAD-complete, meaning that if there were an efficient algorithm for solving it then all other problems in 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 out: it’s theoretically possible that somebody could devise an efficient algorithm for finding Nash equilibria, but most experts aren’t holding their breath. “much of its credibility as a prediction”: Christos Papadimitriou, “The Complexity of Finding Nash Equilibria,” in Nisan et al., Algorithmic Game Theory.

Applied Cryptography: Protocols, Algorithms, and Source Code in C by Bruce Schneier

active measures, cellular automata, Claude Shannon: information theory, complexity theory, dark matter, Donald Davies, Donald Knuth, dumpster diving, Dutch auction, end-to-end encryption, Exxon Valdez, fault tolerance, finite state, heat death of the universe, information security, invisible hand, John von Neumann, knapsack problem, MITM: man-in-the-middle, Multics, NP-complete, OSI model, P = NP, packet switching, quantum cryptography, RAND corporation, RFC: Request For Comment, seminal paper, software patent, telemarketer, traveling salesman, Turing machine, web of trust, Zimmermann PGP

If any DNA survives this screening, it is examined to find the sequence of roads 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 by inspection in a few minutes), the technique is in its infancy and has no forbidding obstacles keeping it from being extended to larger problems.

…

Steven Cook [365] proved that 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 a deterministic polynomial-time algorithm, the proof will show that Satisfiability does not have a deterministic polynomial-time algorithm either. No problem is harder than Satisfiability in NP. Since Cook’s seminal paper was published, a huge number of problems 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 .

…

Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth) Go! Keyword Brief Full Advanced Search Search Tips (Publisher: John Wiley & Sons, Inc.) Author(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 different cities using only one tank of gas (there is a maximum distance he can travel). Is there a route that allows him to visit each city exactly once on that single tank of gas?

21 Recipes for Mining Twitter by Matthew A. Russell

en.wikipedia.org, Google Earth, natural language processing, NP-complete, social web, web application

Analyzing friendship cliques (see http://github.com/ptwobrussell/Recipes-for-Mining -Twitter/blob/master/recipe__clique_analysis.py) # -*- coding: utf-8 -*import sys import json import networkx as nx 50 | The Recipes G = sys.argv[1] g = nx.read_gpickle(G) # # # # Finding cliques is a hard problem, so this could take a while for large graphs. See http://en.wikipedia.org/wiki/NP-complete and http://en.wikipedia.org/wiki/Clique_problem cliques = [c for c in nx.find_cliques(g)] num_cliques = len(cliques) clique_sizes = [len(c) for c in cliques] max_clique_size = max(clique_sizes) avg_clique_size = sum(clique_sizes) / num_cliques max_cliques = [c for c in cliques if len(c) == max_clique_size] num_max_cliques = len(max_cliques) max_clique_sets = [set(c) for c in max_cliques] people_in_every_max_clique = list(reduce(lambda x, y: x.intersection(y), max_clique_sets)) print print print print print print print print print print 'Num 'Avg 'Max 'Num cliques:', num_cliques clique size:', avg_clique_size clique size:', max_clique_size max cliques:', num_max_cliques 'People in all max cliques:' json.dumps(people_in_every_max_clique, indent=4) 'Max cliques:' json.dumps(max_cliques, indent=4) For purposes of illustration, Mining the Social Web (O’Reilly) included an analysis conducted in mid-2010 that determined the following statistics for Tim O’Reilly’s ~700 friendships: Num Avg Max Num Num cliques: 762573 clique size: 14 clique size: 26 max cliques: 6 people in every max clique: 20 Some of the more interesting insight from the analysis was that there are six different cliques of size 26 in Tim O’Reilly’s friendships, which means that those six variations of 26 people all “know” one another to the point that they were at least interested in receiving each other’s status updates in their tweet stream.

…

As an example of practical application, if you wanted to get Tim’s attention at a conference or Maker event, but can’t seem to track him down, you might start looking for one of 1.18 Analyzing Friendship Cliques | 51 these other people since there’s more than a reasonable likelihood that they’re closely connected with him. As a more technical aside, be advised that finding cliques is a hard problem in both a figurative sense, but also in the computational sense that it’s a problem that belongs to a class of problems that are known as NP-Complete. In layman’s terms, being NPComplete means that the combinatorics of the problem, whether it be finding cliques or otherwise, grow explosively as the size of the input for the problem grows. Practically speaking, this means that for a very large graph, you either need to wait a very long time to get an exact answer to the problem of finding cliques, or you need to be willing to settle for an approximate solution.

Hit Refresh: The Quest to Rediscover Microsoft's Soul and Imagine a Better Future for Everyone by Satya Nadella, Greg Shaw, Jill Tracie Nichols

3D printing, AlphaGo, Amazon Web Services, anti-globalists, artificial general intelligence, augmented reality, autonomous vehicles, basic income, Bretton Woods, business process, cashless society, charter city, cloud computing, complexity theory, computer age, computer vision, corporate social responsibility, crowdsourcing, data science, DeepMind, Deng Xiaoping, Donald Trump, Douglas Engelbart, driverless car, Edward Snowden, Elon Musk, en.wikipedia.org, equal pay for equal work, everywhere but in the productivity statistics, fault tolerance, fulfillment center, Gini coefficient, global supply chain, Google Glasses, Grace Hopper, growth hacking, hype cycle, industrial robot, Internet of things, Jeff Bezos, job automation, John Markoff, John von Neumann, knowledge worker, late capitalism, Mars Rover, Minecraft, Mother of all demos, Neal Stephenson, NP-complete, Oculus Rift, pattern recognition, place-making, Richard Feynman, Robert Gordon, Robert Solow, Ronald Reagan, Salesforce, Second Machine Age, self-driving car, side project, Silicon Valley, Skype, Snapchat, Snow Crash, special economic zone, speech recognition, Stephen Hawking, Steve Ballmer, Steve Jobs, subscription business, TED Talk, telepresence, telerobotics, The Rise and Fall of American Growth, The Soul of a New Machine, Tim Cook: Apple, trade liberalization, two-sided market, universal basic income, Wall-E, Watson beat the top human players on Jeopardy!, young professional, zero-sum game

Think of it this way: Imagine coloring the U.S. map so that no state sharing a common border receives the same color. What is the minimal number of colors you would need to accomplish this task? My master’s thesis was about developing the best heuristics to accomplish complex graph coloring in nondeterministic polynomial time, or NP-complete. In other words, how can I solve a problem that has limitless possibilities in a way that is fast and good but not always optimal? Do we solve this as best we can right now, or work forever for the best solution? Theoretical computer science really grabbed me because it showed the limits to what today’s computers can do.

…

Her dad and my father had joined the IAS together and we were family friends. In fact, Anu’s dad and I shared a passion for talking endlessly about cricket, something we continue to this day. He had played for his school and college, captaining both teams. When exactly I fell in love with Anu is what computer scientists would call an NP complete question. I can come up with many times and places but there is no one answer. In other words, it’s complex. Our families were close. Our social circles were the same. As kids we had played together. We overlapped in school and college. Our beloved family dog came from Anu’s family dog’s litter.

…

See also smartphones; and specific products mobility, 42, 43, 54, 58, 70, 73, 88, 108, 216, 225 Mojang, 106–8 Moore, Gordon, 161 Moore’s Law, 140, 161 motion-sensing, 145 Motorola, 72 Mount Rainier, 19 mouse, 142 movable type, 152 Mulally, Alan, 64 multiculturalism, 19 multinational corporations, role of, 12, 235–39 Mundie, Craig, 30, 163 Musk, Elon, 203 Muslims, 19 Myerson, Terry, 3, 82, 105, 109 Myhrvold, Nathan, 30 Nadella, Anu, 7–8, 14, 27, 30–33, 41, 86, 92–93, 114 Nadella, father, 16–18, 20–21, 36, 56 Nadella, mother, 16–18, 20, 22, 86, 114, 181 nano-machines, 228 Nanyuki, Kenya, 99 Napoleonic Wars, 188 Narayen, Shantanu, 20, 136 National Aeronautics and Space Administration (NASA), 144, 146 National Football League (NFL), 10–11 National ICT for Development Policy (Malawi), 216 national security, 174–75, 228 National Security Agency (NSA), 172, 174–75, 181 Native Americans, 156 natural language, 151 Nehru, Jawaharlal, 16 Nepal, 44 Netflix, 30, 126 Netherland (O’Neill), 18 .Net, 58 networking, 45, 49, 213 Neuborne, Burt, 190 New Yorker, 233 New York Times, 24, 80, 176, 195, 209 New Zealand, 78 Nichols, Jill Tracie, 66–67, 95 Nietzsche, Friedrich, 79, 147 Nilekani, Nandan, 222 Nokia, 64, 71–73, 106, 133 nondeterministic polynomial time (NP-complete), 25 North, Douglass, 184 North Dakota, 47 North Korea, 169–70 Novell, 26 Numoto, Takeshi, 59 Obama, Barack, 3, 81, 175–76, 211–12, 214 Obama, Michelle, 211 Oculus Rift, 125, 144 Office, 2, 47, 53–54, 59, 68, 73, 81, 85, 123–25, 137, 203 Office 365, 44–45, 61, 62, 85, 123–25, 152, 233 OneDrive, 121 O’Neill, Joseph, 18 One Microsoft, 102, 108 OneNote, 103, 121 OneWeek growth hack, 103–5 online services, 46–47, 51 open-source, 62, 102 opportunity, 79, 238 Oracle, 3, 26, 81 Orlando nightclub massacre, 117 Osmania University, 36 Outlook, 104, 121 Ozzie, Ray, 46, 52–53 Parthasarathy, Sanjay, 115–16 Partnership on AI, 200 partnerships, 76, 78, 120–38 passion, 92, 94, 100, 103, 242 Pataudi, Tiger, 37 pattern recognition, 54, 150, 152, 201 pay equity, 113–14 PC Revolution, 1, 28, 45, 71, 89, 108, 139, 213 decline of, 66, 70, 79 perception, 150, 152, 154 pharmacies, 218, 223 Phillips, James, 58 PhotoShop, 136 photosynthesis, 160 Pichai, Sundar, 131 pivot tables, 143 Pixar, 13 platform shifts, 76, 142 point-of-sales devices, 128–29 Poland, 223 policymaking, 82, 182, 189–92, 214, 223–28, 235 poverty, 99, 237 Power BI, 121 Powerpoint, 121 Practo, 222 predictive power, 42, 88 Predix platform, 127 printing press, 152 PRISM, 172–73 Prism Skylabs, 153 privacy, 170, 172–80, 186–91, 193–94, 202, 205, 224, 230, 238 probabilistic decision making, 54 productivity, 76, 79, 88, 124, 126, 226–28 product launches, 98–100 public health, 237 public-private partnerships, 225–26 public sector, 222, 228, 237–38 Qatar, 225 Qi Lu, Dr., 51–52 Qualcomm, 3, 80, 131–32 quantum computing, 11, 110, 140–42, 159–67, 209, 212, 239 qubits, 160–61, 164, 166–67 logical, 167 topological, 162, 166 radiation monitoring, 44 railroads, 215 Ramakrishnan, Raghu, 58–59 Ranji Trophy, 38, 40 Rashid, Rick, 30 Reagan, Ronald, 181 Real Madrid, 71 Red Dog, 52–53, 58 Red Hat, 125 Reform Government Surveillance alliance, 174 refugees, 218 regulatory systems, 130, 186–90, 215, 227–28 relational algebra, 26 respect, 135, 202 retailers, 128–29, 153 rice production, 44 Rilke, Rainer Maria, 12 Rise and Fall of American Growth (Gordon), 234 risk-taking, 111, 220 River Runs Through It, A (Maclean), 56 Roberts, John, 185–86 robotics, 13, 145, 149–50, 202–4, 208–9, 228, 231–32, 239 Rochester Institute of Technology, 146 Rocky movies, 44–45 Rogan, Seth, 169 Rolling Stones, 98 Rolls-Royce, 127 Romer, Paul, 229 root-cause analysis, 61 RSA-2048 encryption, 162 Rubinstein, Ira, 32–33 run times, 203 rural areas, connecting, 99 Russia, 172 Russinovich, Mark, 58 Rwanda Vision 2020, 216 safety, 153, 172, 176–80, 182, 185, 188, 194, 228 sales conference, 86–95, 100, 118 Salesforce, 121 Samsung, 132–34 San Bernardino attacks, 177, 179, 189 Sanders, Bernie, 230 Sanskrit, 16, 181 Saudi Arabia, 225 scale, 50, 161 Schiller, Phil, 124 Schmidt, Eric, 26 Scott, Kevin, 82 search and seizure, 185–86 Search Checkpoint #1, 51 search engines, 46–52.

Human Compatible: Artificial Intelligence and the Problem of Control by Stuart Russell

3D printing, Ada Lovelace, AI winter, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Alfred Russel Wallace, algorithmic bias, AlphaGo, Andrew Wiles, artificial general intelligence, Asilomar, Asilomar Conference on Recombinant DNA, augmented reality, autonomous vehicles, basic income, behavioural economics, Bletchley Park, blockchain, Boston Dynamics, brain emulation, Cass Sunstein, Charles Babbage, Claude Shannon: information theory, complexity theory, computer vision, Computing Machinery and Intelligence, connected car, CRISPR, crowdsourcing, Daniel Kahneman / Amos Tversky, data science, deep learning, deepfake, DeepMind, delayed gratification, Demis Hassabis, Elon Musk, en.wikipedia.org, Erik Brynjolfsson, Ernest Rutherford, fake news, Flash crash, full employment, future of work, Garrett Hardin, Geoffrey Hinton, Gerolamo Cardano, Goodhart's law, Hans Moravec, ImageNet competition, Intergovernmental Panel on Climate Change (IPCC), Internet of things, invention of the wheel, job automation, John Maynard Keynes: Economic Possibilities for our Grandchildren, John Maynard Keynes: technological unemployment, John Nash: game theory, John von Neumann, Kenneth Arrow, Kevin Kelly, Law of Accelerating Returns, luminiferous ether, machine readable, machine translation, Mark Zuckerberg, multi-armed bandit, Nash equilibrium, Nick Bostrom, Norbert Wiener, NP-complete, OpenAI, openstreetmap, P = NP, paperclip maximiser, Pareto efficiency, Paul Samuelson, Pierre-Simon Laplace, positional goods, probability theory / Blaise Pascal / Pierre de Fermat, profit maximization, RAND corporation, random walk, Ray Kurzweil, Recombinant DNA, recommendation engine, RFID, Richard Thaler, ride hailing / ride sharing, Robert Shiller, robotic process automation, Rodney Brooks, Second Machine Age, self-driving car, Shoshana Zuboff, Silicon Valley, smart cities, smart contracts, social intelligence, speech recognition, Stephen Hawking, Steven Pinker, superintelligent machines, surveillance capitalism, Thales of Miletus, The Future of Employment, The Theory of the Leisure Class by Thorstein Veblen, Thomas Bayes, Thorstein Veblen, Tragedy of the Commons, transport as a service, trolley problem, Turing machine, Turing test, universal basic income, uranium enrichment, vertical integration, Von Neumann architecture, Wall-E, warehouse robotics, Watson beat the top human players on Jeopardy!, web application, zero-sum game

An improved algorithm for propositional inference: Martin Davis, George Logemann, and Donald Loveland, “A machine program for theorem-proving,” Communications of the ACM 5 (1962): 394–97. 4. The satisfiability problem—deciding whether a collection of sentences is true in some world—is NP-complete. The reasoning problem—deciding whether a sentence follows from the known sentences—is co-NP-complete, a class that is thought to be harder than NP-complete problems. 5. There are two exceptions to this rule: no repetition (a stone may not be played that returns the board to a situation that existed previously) and no suicide (a stone may not be placed such that it would immediately be captured—for example, if it is already surrounded). 6.

…

Now write a program Q that calls LoopChecker as a subroutine, with Q itself and X as inputs, and then does the opposite of what LoopChecker(Q,X) predicts. So, if LoopChecker says that Q halts, Q doesn’t halt, and vice versa. Thus, the assumption that LoopChecker exists leads to a contradiction, so LoopChecker cannot exist. 40. I say “appear” because, as yet, the claim that the class of NP-complete problems requires superpolynomial time (usually referred to as P ≠ NP) is still an unproven conjecture. After almost fifty years of research, however, nearly all mathematicians and computer scientists are convinced the claim is true. 41. Lovelace’s writings on computation appear mainly in her notes attached to her translation of an Italian engineer’s commentary on Babbage’s engine: L.

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

AlphaGo, Amazon Mechanical Turk, Bayesian statistics, centre right, combinatorial explosion, constrained optimization, correlation coefficient, crowdsourcing, data science, deep learning, DeepMind, duck typing, en.wikipedia.org, Geoffrey Hinton, iterative process, Netflix Prize, NP-complete, optical character recognition, P = NP, p-value, pattern recognition, performance metric, recommendation engine, self-driving car, SpamAssassin, speech recognition, statistical model

Solutions to these exercises are available in Appendix A. 1 Graphviz is an open source graph visualization software package, available at http://www.graphviz.org/. 2 P is the set of problems that can be solved in polynomial time. NP is the set of problems whose solutions 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 reduction of entropy is often called an information gain. 5 See Sebastian Raschka’s interesting analysis for more details. 6 It randomly selects the set of features to evaluate at each node.

…

Warning As you can see, the CART algorithm is a greedy algorithm: it greedily searches for an optimum split at the top level, then repeats the process at each level. It does not check whether or not the split will lead to the lowest possible impurity several levels down. A greedy algorithm often 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 a “reasonably good” solution. Computational Complexity Making predictions requires traversing the Decision Tree from the root to a leaf. Decision Trees are generally approximately balanced, so traversing the Decision Tree requires going through roughly O(log2(m)) nodes.3 Since each node only requires checking the value of one feature, the overall prediction complexity is just O(log2(m)), independent of the number of features.

Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age by Steven Levy

Albert Einstein, Bletchley Park, Claude Shannon: information theory, cognitive dissonance, Compatible Time-Sharing System, computer age, disinformation, Donald Knuth, Eratosthenes, Extropian, Fairchild Semiconductor, information security, invention of the telegraph, Jim Simons, John Gilmore, John Markoff, John Perry Barlow, Kevin Kelly, knapsack problem, Marc Andreessen, Mitch Kapor, MITM: man-in-the-middle, Mondo 2000, Network effects, new economy, NP-complete, quantum cryptography, Ronald Reagan, Saturday Night Live, Silicon Valley, Simon Singh, Stephen Hawking, Steven Levy, Watson beat the top human players on Jeopardy!, web of trust, Whole Earth Catalog, zero-sum game, Zimmermann PGP, éminence grise

Could this phenomenon be the basis for a devilishly challenging one-way function? Though Diffie and Hellman did not choose to pursue this idea, others would. Another alternative involved computational complexity, and Diffie pored over a book on the subject, particularly a chapter on what was known as NP-complete functions. The class of NP-complete problems, Diffie later wrote, are “problems thought not to be solvable in polynomial time on any deterministic computer.” This meant that they were so hard that you could set your Macintosh, or even your Cray supercomputer (if you were the NSA), to work on the problem and when you checked the results a few trillion years later, you wouldn’t even be in the general neighborhood of solving it.

…

“I was basically isolated until I met Whit and Marty,” he says. “I was ready to keep banging away until I got some response, but there was no one else who was interested in pursuing this.” Merkle arrived at Stanford convinced that his most promising idea revolved around a scheme built around finding trapdoor one-way functions involving the NP-complete problem. The system was built around a mathematical problem known as knapsacks. To understand his scheme, picture, naturally, a knapsack. “The idea is to put things into this knapsack, to exactly fill it to the brim without going either over or under,” he says. Diffie would later describe the problem as that of a shipping clerk faced with a collection of packages of various sizes and shapes who had to find the absolute best way to stuff the packages in the mailbag.

…

., ref-1, ref-2, ref-3 Mosaic, ref-1 “Multiuser Cryptographic Techniques” (Diffie and Hellman), ref-1, ref-2, ref-3 Murray, Patty, ref-1 Myhrvold, Nathan, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Mykotronx, ref-1, ref-2, ref-3 National Bureau of Standards (NBS), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 National Institute of Standards and Technology (NIST), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 National Research Council (NRC), ref-1, ref-2 National Science Foundation (NSF), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 National Security Access Field (NSAF), ref-1 National Security Agency (NSA), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22, ref-23, ref-24, ref-25, ref-26, ref-27, ref-28, ref-29, ref-30, ref-31, ref-32, ref-33 Clipper and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 DES and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9 Diffie and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 dual roles of, ref-1 GCHQ and, ref-1, ref-2 Kahn and, ref-1, ref-2 Lotus Notes and, ref-1, ref-2, ref-3, ref-4 NRC report and, ref-1 NSAF and, ref-1 Project Overtake of, ref-1 security failures at, ref-1 Snuffle and, ref-1 National Security Decision Directive, ref-1 Nelson, Mike, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Netscape, ref-1, ref-2, ref-3 Neukom, Bill, ref-1 “New Directions in Cryptography” (Diffie and Hellman), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 New York Times, ref-1, ref-2 Nicolai, Carl, ref-1, ref-2 nonrepudiation feature, ref-1 nonsecret encryption, ref-1 Notes, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8 NP-complete functions, ref-1, ref-2 O’Brien, Bart, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Odom, William E., ref-1 Omura, Jim, ref-1, ref-2 one-time pads, ref-1, ref-2, ref-3 one-way functions, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 factoring, ref-1, ref-2, ref-3 knapsacks, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 trapdoor, ref-1, ref-2, ref-3, ref-4 Ozzie, Ray, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 paranoia levels, ref-1 Parker, Donn, ref-1, ref-2 passwords, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Pasta, John R., ref-1 Patel, Marilyn, ref-1 patents, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22 Patterson, Nick, ref-1, ref-2, ref-3, ref-4 Penet, ref-1, ref-2, ref-3, ref-4, ref-5 Phasorphone, ref-1 Podesta, John, ref-1, ref-2 Poe, Edgar Allan, ref-1, ref-2, ref-3 pornography, ref-1 Press, Frank, ref-1 Pretty Good Privacy (PGP), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12 breaking of, ref-1, ref-2 Prime, Geoffrey, ref-1 prime numbers, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Project C43, ref-1, ref-2 Project Overtake, ref-1 public key cryptography, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22, ref-23, ref-24, ref-25, ref-26 certification of, ref-1 escrow and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 nonsecret encryption and, ref-1 Secure Sockets Layer, ref-1, ref-2, ref-3 security failures and, ref-1 Public Key Partners (PKP), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Puzzle Palace, The (Bamford), ref-1, ref-2 quantum computers, ref-1 Random Number Generator (RNG), ref-1 Ray, Charles, ref-1 RC-2, ref-1, ref-2, ref-3 RC-4, ref-1, ref-2, ref-3, ref-4 Reagan, Ronald, ref-1, ref-2 Reeds, Jim, ref-1 remailers (anonymous servers), ref-1, ref-2, ref-3, ref-4, ref-5 Penet, ref-1, ref-2, ref-3, ref-4, ref-5 Richardson, Elliot, ref-1 Ritner, Peter, ref-1, ref-2 Rivest, Ron, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20 Rizzo, Paul, ref-1 Roberts, Larry, ref-1 Robinson, William B., ref-1, ref-2 Rohrbacher, Dana, ref-1 Rosenblum, Howard, ref-1, ref-2 Rotenberg, Marc, ref-1, ref-2 RSA, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22, ref-23, ref-24, ref-25, ref-26, ref-27, ref-28, ref-29, ref-30, ref-31 Netscape and, ref-1 patents for, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 personal computers and, ref-1, ref-2 RSA Data Security, Inc., ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16 conference of, ref-1, ref-2, ref-3, ref-4 Sacco, Luigi, ref-1 Safire, William, ref-1 S-boxes (substitution boxes), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Schiller, Jeff, ref-1 Schneier, Bruce, ref-1, ref-2, ref-3 Schnorr, Claus, ref-1, ref-2 Schroeppel, Richard, ref-1, ref-2, ref-3, ref-4 Schwartz, John J., ref-1 Science, ref-1, ref-2, ref-3, ref-4 Scientific American, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8 Scientologists, ref-1, ref-2, ref-3 search warrants, ref-1, ref-2, ref-3, ref-4 secret sharing, ref-1 Secure Sockets Layer (SSL), ref-1, ref-2, ref-3 Security and Freedom through Encryption (SAFE) bill, ref-1, ref-2, ref-3 Security Dynamics, ref-1 Senate Bill ref-1, ref-2, ref-3, ref-4 servers, ref-1, ref-2 anonymous, see remailers Sessions, William, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Shamir, Adi, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17 Shannon, Claude, ref-1, ref-2, ref-3, ref-4, ref-5 shareware, ref-1, ref-2 signals intelligence, ref-1 signatures, digital, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13 blind, ref-1, ref-2 DSA, ref-1, ref-2, ref-3 Silver, Roland, ref-1, ref-2, ref-3, ref-4 Simmons, Gus, ref-1 Simons, Jim, ref-1, ref-2 Skipjack, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 Snefru, ref-1 Snow, Brian, ref-1 Snuffle, ref-1 stream ciphers, ref-1 Studeman, William O., ref-1, ref-2 substitution boxes (S-boxes), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 SWIFT, ref-1 T Attack (differential cryptanalysis), ref-1, ref-2, ref-3 telephones: cellular, ref-1 security devices for, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 Tempest technology, ref-1 Tenet, George, ref-1 Tessera, ref-1 threshold scheme, ref-1 Time, ref-1 time-sharing, ref-1, ref-2 toll payments, ref-1 trapdoors, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9 knapsacks, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 one-way function, ref-1, ref-2, ref-3, ref-4 Senate bill and, ref-1, ref-2, ref-3 Tritter, Alan, ref-1, ref-2, ref-3, ref-4 Tuchman, Walter, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 univectors, ref-1, ref-2 Usenet, ref-1, ref-2 vector space, ref-1 VeriSign, ref-1 Very Large Scale Integration (VLSI), ref-1 ViaCrypt, ref-1 virtual private networks, ref-1 Wagner, Dave, ref-1 Walker, Steve, ref-1 Wall Street Journal, ref-1, ref-2 Warren, Jim, ref-1, ref-2 Washington Post, ref-1 web of trust, ref-1 Weingarten, Fred, ref-1 Weldon, Curt, ref-1 Williamson, Malcolm, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Windows, ref-1 wiretapping, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Wise, William, ref-1 World Wide Web, ref-1, ref-2 browsers for, ref-1, ref-2, ref-3 Wormser, Dave, ref-1 Wylie, Shawn, ref-1 Xerox Corporation, ref-1, ref-2 xor operations, ref-1 Zero Knowledge, ref-1 zero-knowledge proofs of identity, ref-1 Zimmermann, Kacie, ref-1 Zimmermann, Phil, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 contents acknowledgments preface the loner the standard public key prime time selling crypto patents and keys crypto anarchy the clipper chip slouching toward crypto epilogue: the open secret notes bibliography glossary index VIKING Published by the Penguin Group Penguin Putnam Inc., 375 Hudson Street, New York, New York 10014, U.S.A.

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

active measures, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, AltaVista, Charles Babbage, complexity theory, dark matter, data acquisition, Donald Knuth, fault tolerance, information security, MITM: man-in-the-middle, NP-complete, OSI model, Silicon Valley, speech recognition, Turing complete, Turing machine, Vannevar Bush

What could one gain from this? Wouldn’t it be as much fun to solve them yourself? Of course, the answer is quite interesting. First, there is a business to solving puzzles with 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 computing power, clever algorithms, or both—would likely take a lucky inventor one step closer to world domination. There’s the incentive, then, but how would one do it?

…

Finding solutions to SAT problems boils down to determining a set of values for all variables in the equation, for which the whole formula that incorporates those variables has a logic value of truth. Although trivial SAT problems like the one shown earlier are easy to solve, even without invoking any solving mechanism other than trial and error, more complex multivariable cases are indeed NP complete, and, consequently, other NP problems can be reduced to SAT problems in polynomial (meaning sane) time. And here lies the problem. We can formulate a hard NP problem in terms of SAT, but this does not buy us much. As of this writing, when it comes to a non-trivial equation, even the best SAT-solving algorithms known aren’t much more effective than a brute-force search whereby all possibilities are tried, and the value of the formula is evaluated for each possibility.

…

This means that the time needed to solve a polynomial problem corresponds directly to the input length raised to a constant exponent, which can be zero (causing the time not to depend on input length at all, as with testing for parity). Non-polynomial (NP) problems have no known solutions of this nature and may require dramatically more time to solve as the input length increases, exhibiting, for example, exponential dependency. A subset of NP problems, known as NP complete, are proven to have no polynomial time solutions. NP problems are generally regarded as “hard” for nontrivial inputs, whereas P problems are less expensive to solve. Practical Considerations . . . or, perhaps, not just yet. The approach suggested in the aforementioned research is revolutionary and interesting, but not necessarily a particularly practical way to build a supercomputer by stealing from the rich.

Hands-On Machine Learning With Scikit-Learn and TensorFlow: Concepts, Tools, and Techniques to Build Intelligent Systems by Aurélien Géron

AlphaGo, Amazon Mechanical Turk, Anton Chekhov, backpropagation, combinatorial explosion, computer vision, constrained optimization, correlation coefficient, crowdsourcing, data science, deep learning, DeepMind, don't repeat yourself, duck typing, Elon Musk, en.wikipedia.org, friendly AI, Geoffrey Hinton, ImageNet competition, information retrieval, iterative process, John von Neumann, Kickstarter, machine translation, natural language processing, Netflix Prize, NP-complete, OpenAI, optical character recognition, P = NP, p-value, pattern recognition, pull request, recommendation engine, self-driving car, sentiment analysis, SpamAssassin, speech recognition, stochastic process

Solutions to these exercises are available in Appendix A. 1 Graphviz is an open source graph visualization software package, available at http://www.graphviz.org/. 2 P is the set of problems that can be solved in polynomial time. NP is the set of problems whose solutions 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 reduction of entropy is often called an information gain. 5 See Sebastian Raschka’s interesting analysis for more details. 6 It randomly selects the set of features to evaluate at each node.

…

Warning As you can see, the CART algorithm is a greedy algorithm: it greedily searches for an optimum split at the top level, then repeats the process at each level. It does not check whether or not the split will lead to the lowest possible impurity several levels down. A greedy algorithm often 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 a “reasonably good” solution. Computational Complexity Making predictions requires traversing the Decision Tree from the root to a leaf. Decision Trees are generally approximately balanced, so traversing the Decision Tree requires going through roughly O(log2(m)) nodes.3 Since each node only requires checking the value of one feature, the overall prediction complexity is just O(log2(m)), independent of the number of features.

…

Pac-Man Using Deep Q-Learning min_after_dequeue, RandomShuffleQueue MNIST dataset, MNIST-MNIST model parallelism, Model Parallelism-Model Parallelism model parameters, Gradient Descent, Batch Gradient Descent, Early Stopping, Under the Hood, Quadratic Programming, Creating Your First Graph and Running It in a Session, Construction Phase, Training RNNsdefining, Model-based learning model selection, Model-based learning model zoos, Model Zoos model-based learning, Model-based learning-Model-based learning modelsanalyzing, Analyze the Best Models and Their Errors-Analyze the Best Models and Their Errors evaluating on test set, Evaluate Your System on the Test Set-Evaluate Your System on the Test Set moments, Adam Optimization Momentum optimization, Momentum optimization-Momentum optimization Monte Carlo tree search, Policy Gradients Multi-Layer Perceptrons (MLP), Introduction to Artificial Neural Networks, The Perceptron-Multi-Layer Perceptron and Backpropagation, Neural Network Policiestraining with TF.Learn, Training an MLP with TensorFlow’s High-Level API multiclass classifiers, Multiclass Classification-Multiclass Classification Multidimensional Scaling (MDS), Other Dimensionality Reduction Techniques multilabel classifiers, Multilabel Classification-Multilabel Classification Multinomial Logistic Regression (see Softmax Regression) multinomial(), Neural Network Policies multioutput classifiers, Multioutput Classification-Multioutput Classification MultiRNNCell, Distributing a Deep RNN Across Multiple GPUs multithreaded readers, Multithreaded readers using a Coordinator and a QueueRunner-Multithreaded readers using a Coordinator and a QueueRunner multivariate regression, Frame the Problem N naive Bayes classifiers, Multiclass Classification name scopes, Name Scopes natural language processing (NLP), Recurrent Neural Networks, Natural Language Processing-An Encoder–Decoder Network for Machine Translationencoder-decoder network for machine translation, An Encoder–Decoder Network for Machine Translation-An Encoder–Decoder Network for Machine Translation TensorFlow tutorials, Natural Language Processing, An Encoder–Decoder Network for Machine Translation word embeddings, Word Embeddings-Word Embeddings Nesterov Accelerated Gradient (NAG), Nesterov Accelerated Gradient-Nesterov Accelerated Gradient Nesterov momentum optimization, Nesterov Accelerated Gradient-Nesterov Accelerated Gradient network topology, Fine-Tuning Neural Network Hyperparameters neural network hyperparameters, Fine-Tuning Neural Network Hyperparameters-Activation Functionsactivation functions, Activation Functions neurons per hidden layer, Number of Neurons per Hidden Layer number of hidden layers, Number of Hidden Layers-Number of Hidden Layers neural network policies, Neural Network Policies-Neural Network Policies neuronsbiological, From Biological to Artificial Neurons-Biological Neurons logical computations with, Logical Computations with Neurons neuron_layer(), Construction Phase next_batch(), Execution Phase No Free Lunch theorem, Testing and Validating node edges, Visualizing the Graph and Training Curves Using TensorBoard nonlinear dimensionality reduction (NLDR), LLE(see also Kernel PCA; LLE (Locally Linear Embedding)) nonlinear SVM classification, Nonlinear SVM Classification-Computational Complexitycomputational complexity, Computational Complexity Gaussian RBF kernel, Gaussian RBF Kernel-Gaussian RBF Kernel with polynomial features, Nonlinear SVM Classification-Polynomial Kernel polynomial kernel, Polynomial Kernel-Polynomial Kernel similarity features, adding, Adding Similarity Features-Adding Similarity Features nonparametric models, Regularization Hyperparameters nonresponse bias, Nonrepresentative Training Data nonsaturating activation functions, Nonsaturating Activation Functions-Nonsaturating Activation Functions normal distribution (see Gaussian distribution) Normal Equation, The 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 Compute Capability, Installation nvidia-smi, Managing the GPU RAM n_components, Choosing the Right Number of Dimensions O observation space, Neural Network Policies off-policy algorithm, Temporal Difference Learning and Q-Learning offline learning, Batch learning one-hot encoding, Handling Text and Categorical Attributes one-versus-all (OvA) strategy, Multiclass Classification, Softmax Regression, Exercises one-versus-one (OvO) strategy, Multiclass Classification online learning, Online learning-Online learning online SVMs, Online SVMs-Online SVMs OpenAI Gym, Introduction to OpenAI Gym-Introduction to OpenAI Gym operation_timeout_in_ms, In-Graph Versus Between-Graph Replication Optical Character Recognition (OCR), The Machine Learning Landscape optimal state value, Markov Decision Processes optimizers, Faster Optimizers-Learning Rate SchedulingAdaGrad, AdaGrad-AdaGrad Adam optimization, Faster Optimizers, Adam Optimization-Adam Optimization Gradient Descent (see Gradient Descent optimizer) learning rate scheduling, Learning Rate Scheduling-Learning Rate Scheduling Momentum optimization, Momentum optimization-Momentum optimization Nesterov Accelerated Gradient (NAG), Nesterov Accelerated Gradient-Nesterov Accelerated Gradient RMSProp, RMSProp out-of-bag evaluation, Out-of-Bag Evaluation-Out-of-Bag Evaluation out-of-core learning, Online learning out-of-memory (OOM) errors, Static Unrolling Through Time out-of-sample error, Testing and Validating OutOfRangeError, Reading the training data directly from the graph, Multithreaded readers using a Coordinator and a QueueRunner output gate, LSTM Cell output layer, Multi-Layer Perceptron and Backpropagation OutputProjectionWrapper, Training to Predict Time Series-Training to Predict Time Series output_put_keep_prob, Applying Dropout overcomplete autoencoder, Unsupervised Pretraining Using Stacked Autoencoders overfitting, Overfitting the Training Data-Overfitting the Training Data, Create a Test Set, Soft Margin Classification, Gaussian RBF Kernel, Regularization Hyperparameters, Regression, Number of Neurons per Hidden Layeravoiding through regularization, Avoiding Overfitting Through Regularization-Data Augmentation P p-value, Regularization Hyperparameters PaddingFIFOQueue, PaddingFifoQueue Pandas, Create the Workspace, Download the Datascatter_matrix, Looking for Correlations-Looking for Correlations parallel distributed computing, Distributing TensorFlow Across Devices and Servers-Exercisesdata parallelism, Data Parallelism-TensorFlow implementation in-graph versus between-graph replication, In-Graph Versus Between-Graph Replication-Model Parallelism model parallelism, Model Parallelism-Model Parallelism multiple devices across multiple servers, Multiple Devices Across Multiple Servers-Other convenience functionsasynchronous communication using queues, Asynchronous Communication Using TensorFlow Queues-PaddingFifoQueue loading training data, Loading Data Directly from the Graph-Other convenience functions master and worker services, The Master and Worker Services opening a session, Opening a Session pinning operations across tasks, Pinning Operations Across Tasks sharding variables, Sharding Variables Across Multiple Parameter Servers sharing state across sessions, Sharing State Across Sessions Using Resource Containers-Sharing State Across Sessions Using Resource Containers multiple devices on a single machine, Multiple Devices on a Single Machine-Control Dependenciescontrol dependencies, Control Dependencies installation, Installation-Installation managing the GPU RAM, Managing the GPU RAM-Managing the GPU RAM parallel execution, Parallel Execution-Parallel Execution placing operations on devices, Placing Operations on Devices-Soft placement one neural network per device, One Neural Network per Device-One Neural Network per Device parameter efficiency, Number of Hidden Layers parameter matrix, Softmax Regression parameter server (ps), Multiple Devices Across Multiple Servers parameter space, Gradient Descent parameter vector, Linear Regression, Gradient Descent, Training and Cost Function, Softmax Regression parametric models, Regularization Hyperparameters partial derivative, Batch Gradient Descent partial_fit(), Incremental PCA Pearson's r, Looking for Correlations peephole connections, Peephole Connections penalties (see rewards, in RL) percentiles, Take a Quick Look at the Data Structure Perceptron convergence theorem, The Perceptron Perceptrons, The Perceptron-Multi-Layer Perceptron and Backpropagationversus Logistic Regression, The Perceptron training, The Perceptron-The Perceptron performance measures, Select a Performance Measure-Select a Performance Measureconfusion matrix, Confusion Matrix-Confusion Matrix cross-validation, Measuring Accuracy Using Cross-Validation-Measuring Accuracy Using Cross-Validation precision and recall, Precision and Recall-Precision/Recall Tradeoff ROC (receiver operating characteristic) curve, The ROC Curve-The ROC Curve performance scheduling, Learning Rate Scheduling permutation(), Create a Test Set PG algorithms, Policy Gradients photo-hosting services, Semisupervised learning pinning operations, Pinning Operations Across Tasks pip, Create the Workspace Pipeline constructor, Transformation Pipelines-Select and Train a Model pipelines, Frame the Problem placeholder nodes, Feeding Data to the Training Algorithm placers (see simple placer; dynamic placer) policy, Policy Search policy gradients, Policy Search (see PG algorithms) policy space, Policy Search polynomial features, adding, Nonlinear SVM Classification-Polynomial Kernel polynomial kernel, Polynomial Kernel-Polynomial Kernel, Kernelized SVM Polynomial Regression, Training Models, Polynomial Regression-Polynomial Regressionlearning curves in, Learning Curves-Learning Curves pooling kernel, Pooling Layer pooling layer, Pooling Layer-Pooling Layer power scheduling, Learning Rate Scheduling precision, Confusion Matrix precision and recall, Precision and Recall-Precision/Recall TradeoffF-1 score, Precision and Recall-Precision and Recall precision/recall (PR) curve, The ROC Curve precision/recall tradeoff, Precision/Recall Tradeoff-Precision/Recall Tradeoff predetermined piecewise constant learning rate, Learning Rate Scheduling predict(), Data Cleaning predicted class, Confusion Matrix predictions, Confusion Matrix-Confusion Matrix, Decision Function and Predictions-Decision Function and Predictions, Making Predictions-Estimating Class Probabilities predictors, Supervised learning, Data Cleaning preloading training data, Preload the data into a variable PReLU (parametric leaky ReLU), Nonsaturating Activation Functions preprocessed attributes, Take a Quick Look at the Data Structure pretrained layers reuse, Reusing Pretrained Layers-Pretraining on an Auxiliary Taskauxiliary task, Pretraining on an Auxiliary Task-Pretraining on an Auxiliary Task caching frozen layers, Caching the Frozen Layers freezing lower layers, Freezing the Lower Layers model zoos, Model Zoos other frameworks, Reusing Models from Other Frameworks TensorFlow model, Reusing a TensorFlow Model-Reusing a TensorFlow Model unsupervised pretraining, Unsupervised Pretraining-Unsupervised Pretraining upper layers, Tweaking, Dropping, or Replacing the Upper Layers Pretty Tensor, Up and Running with TensorFlow primal problem, The Dual Problem principal component, Principal Components Principal Component Analysis (PCA), PCA-Randomized PCAexplained variance ratios, Explained Variance Ratio finding principal components, Principal Components-Principal Components for compression, PCA for Compression-Incremental PCA Incremental PCA, Incremental PCA-Randomized PCA Kernel PCA (kPCA), Kernel PCA-Selecting a Kernel and Tuning Hyperparameters projecting down to d dimensions, Projecting Down to d Dimensions Randomized PCA, Randomized PCA Scikit Learn for, Using Scikit-Learn variance, preserving, Preserving the Variance-Preserving the Variance probabilistic autoencoders, Variational Autoencoders probabilities, estimating, Estimating Probabilities-Estimating Probabilities, Estimating Class Probabilities producer functions, Other convenience functions projection, Projection-Projection propositional logic, From Biological to Artificial Neurons pruning, Regularization Hyperparameters, Symbolic Differentiation Pythonisolated environment in, Create the Workspace-Create the Workspace notebooks in, Create the Workspace-Download the Data pickle, Better Evaluation Using Cross-Validation pip, Create the Workspace Q Q-Learning algorithm, Temporal Difference Learning and Q-Learning-Learning to Play Ms.

Data Mining in Time Series Databases by Mark Last, Abraham Kandel, Horst Bunke

backpropagation, call centre, computer vision, discrete time, G4S, information retrieval, iterative process, NP-complete, p-value, pattern recognition, random walk, sensor fusion, speech recognition, web application

Median Strings: A Review 191 14. Guyon, Schomaker, L., Plamondon, R., Liberman, M. and Janet, S. (1994). UNIPEN Project on On-Line Exchange and Recognizer Benchmarks. Proc. of 12th Int. Conf. on Pattern Recognition, pp. 29–33. 15. de la Higuera, C. and Casacuberta, F. (2000). Topology of Strings: Median String is NP-Complete. Theoretical Computer Science, 230(1/2), 39–48. 16. Jiang, X., Schiffmann, L., and Bunke, H. (2000). Computation of Median Shapes. Proc. of 4th. Asian Conf. on Computer Vision, pp. 300–305, Taipei. 17. Jiang, X., Abegglen, K., and Bunke, H. (2001). Genetic Computation of Generalized Median Strings.

…

A Mean String Algorithm to Compute the Average Among a Set of 2D Shapes. Pattern Recognition Letters, 23(1–3), 203–213. 34. Sankoff, D. and Kruskal, J.B. (1983). (eds.). Time Warps, String Edits, and Macromolecules: The Theory and Practice of String Comparison, AddisonWesley. 35. Sim, J.S. and Park, K. (2001). The Consensus String Problem for a Metric is NP-Complete. Journal of Discrete Algorithms, 2(1). 36. Stephen, G.A. (1994). String Searching Algorithms, World Scientific. 37. Subramanyan, K. and Dean, D. (2000). A Procedure to Average 3D Anatomical Structures. Medical Image Analysis, 4(4), 317–334. 38. Wagner, R.A. and Fischer, M.J. (1974). The String-to-String Correction Problem.

Concepts, Techniques, and Models of Computer Programming by Peter Van-Roy, Seif Haridi

computer age, Debian, discrete time, Donald Knuth, Eratosthenes, fault tolerance, functional programming, G4S, general-purpose programming language, George Santayana, John von Neumann, Lao Tzu, Menlo Park, natural language processing, NP-complete, Paul Graham, premature optimization, sorting algorithm, the Cathedral and the Bazaar, Therac-25, Turing complete, Turing machine, type inference

For example, games with realistic graphics, which by definition are always at the edge of what is possible. Other problems are expensive for more fundamental reasons. For example, NP-complete problems. These problems are in the class NP, i.e., it is easy to check a solution, if you are given a candidate.14 But finding a solution may be much harder. A simple example is the circuit satisfiability problem. Given a combinational digital circuit that consists of And, Or, and Not gates, does there exist a set of input values that makes the output 1? This problem is NP-complete [47]. An NP-complete problem is a special kind of NP problem with the property that if you can solve one in polynomial time, then you can solve all in polynomial time.

…

An NP-complete problem is a special kind of NP problem with the property that if you can solve one in polynomial time, then you can solve all in polynomial time. Many computer scientists have tried over several decades to find polynomial-time solutions to NP-complete problems, 13. Kurzweil claims that the growth rate is increasing and will lead to a “singularity” somewhere near the middle of the 21st century. 14. NP stands for “nondeterministic polynomial time.” 3.6 Higher-order programming 177 and none have succeeded. Therefore, most computer scientists suspect that NPcomplete problems cannot be solved in polynomial time. In this book, we will not talk any more about computationally expensive problems.

…

Paul, 257 Mozart Consortium, xxiv, xxvi, 106 Mozart Programming System, 254 Base modules, 229, 729 Browser tool, 1, 88 displaying cyclic structures, 102 displaying strings, 716 WaitQuiet operation, 798 cheap concurrency, 252 command line interface, 817 Compiler Panel tool, 815 Distribution Panel tool, 815 Explorer tool, 757, 815 garbage collection, 78 GlobalStore, 743 interactive interface, 1, 87, 815 kernel languages, 844 library modules, 229 limited role of the compiler, 504 memory consumption, 174 Open Source license, xxiv overview, xxiv Panel tool, 815 performance, 201, 379 Prototyper tool, 689 separate compilation, 457 Standard Library, 214, 225, 230, 685, 690 System modules, 229, 729 thread scheduler, 253 uncaught exception, 93, 801 multi-agent systems (MAS), xxiii, 345, 362, 576 multimedia, 176 multiprocessor cluster, 711 shared-memory, 710 multiset, 240 mutable store (for cells), 794 Myriorama, 273 n-queens problem, 629 name, 203, 714, 791, 824, 847 defining scope, 508 distributed computing, 711 fresh, 203 generation, 206 impure, 715 pure, 715 name server, 403, 711 natural design, 461, 569 natural language, xiii, 31, 38, 641 natural selection, 451, 462 Naur, Peter, 32 Index 885 needed variable, 283, 796 negation as failure, 662, 674 nesting marker, 53, 83, 355, 365 Netherlands, 819 network awareness, 387, 723 network transparency, 255, 387, 708 neutral element, 187 New operation, 495, 549 NewActive operation, 558 NewActiveExc operation, 562, 728 NewArray operation, 436 NewCell operation, 416 NewDictionary operation, 437 NewLock operation, 22, 583 NewName operation, 203, 792, 824 NewPort operation, 349 NewSpace operation, 764 NewStat operation, 725 resilient, 742 Newton’s method for square roots, 119 Newton, Isaac, 278 nil, 828 node (in Erlang), 387 noise (electronic), 473 nonblocking operation, 333 receive (in Erlang), 394 delete (in queue), 598 read (in tuple space), 586 receive, 333 send, 333 stack, 578 noncompositional design, 461 nondeterminism choice statement, 621, 623, 772 declarative concurrent model, 575 don’t know, 324, 621 introduction, 20 limitation of declarative model, 319 logic programming, 638 observable, 20, 234, 319, 570, 573, 575, 576 bounded buffer, 595 Filter operation, 386 lack of in Flavius Josephus problem, 561 relation to exceptions, 327 relation to coroutines, 275 thread scheduler, 253 nonstrict evaluation, 331 Haskell, 310 nonvar operation (in Prolog), 660, 662 normal distribution, 476 normal order reduction, 330 Haskell, 309 notify operation (in monitor), 592 notifyAll operation (in monitor), 593 NP-complete problems, 176 NUL character, 841 number, 52, 819 O’Keefe, Richard, 111, 407, 668 object, 413, 420, 542, 546 declarative, 423, 483, 568 introduction, 17 Java, 551, 807 passive, 556, 575, 576 strong, 542 object code, 221 object graph, 553 object, active, 350, 556–567 comparison with passive object, 556 defining behavior with a class, 558 polymorphism, 429 object, port, 346, 350, 413 approaches to concurrency, 573 Erlang, 563 further reading, 582 many-to-one communication, 351 polymorphism, 429 reactive, 351 reasoning, 352 886 Index sharing one thread, 378 when to use, 576 object, stream, 256, 265–266, 411, 413, 574 comparison with port object, 351 Flavius Josephus problem, 561 higher-order iteration, 258 polymorphism, 429 producer/consumer, 257 transducer, 259 Ockham, William of, 29 octal integer, 819 Okasaki, Chris, 175, 330 OLE (Object Linking and Embedding), 462 OMG (Object Management Group), 462 open distribution, 709, 711, 714 open program, 202 Open Source software, xxiv operating system, 208 Linux, xxvi, 201, 471, 499 Mac OS X, xxiv, xxvi, 254 Solaris, xxvi, xxix Unix, xxiv, 254, 305, 459, 553, 642 VM (Virtual Machine), 41 Windows, xxiv, 254 operation (in data abstraction), 420 operational semantics, 38, 60, 635, 779–811 operator associativity, 34, 837 binary, 34, 836 infix, 52, 83, 185, 793, 826, 828, 830, 836 mixfix, 826, 837 postfix, 837 precedence, 34, 836 prefix, 836 ternary, 838 unary, 836 OPI (Oz programming interface), 815 optimistic scheduling, 603 optimization, 177 avoid during development, 452 combinatoric, 661 compiler, 162 eager execution, 302 early error detection, 504 first-argument indexing, 659 memoization, 694 monitor performance, 597 object system, 545 relational programming, 622 short-circuit protocol, 559 standard computer, 314 thread priorities, 265 order-independence, 49 unification, 110, 232 orelse operator, 83 otherwise method, 500 OTP (Ericsson Open Telecom Platform), 386 overloading, 313, 429 overriding relation, 502 Oz, Wizard of, 1 ozc command, 228, 817 pairwise distinct, 756, 774, 782 palindrome, 628 palindrome product problem, 628, 757 Panangaden, Prakash, 338 Panel tool, see Mozart Programming System Papert, Seymour, xiii, 233 paradigm, xiii, xvi, see computation model declarative, 29 school of thought, xvi paragraph (in OPI), 815 parallelism, 237, 322 difference with concurrency, 322 importance of nonstrictness, 331 importance of worst-case complexity, 174 parameter passing, 430–434 Index 887 call by name, 432 exercise, 484 call by need, 433 exercise, 485 lazy evaluation, 433 call by reference, 57, 430 Java, 555 call by value, 431 Java, 555 call by value-result, 431 call by variable, 430 parity, 14 Parnas, David Lorge, xxii, 462 parser, 32, 161–166 generic, 650 gump tool, 39 natural language, 641 partial failure, 326 partial list, 440, 829 partial order, 238 partial termination, 243, 338, 804 partial value, 46 Pascal’s triangle, 4 Pascal, Blaise, 5 pass by . . . , see parameter passing pattern matching case statement, 6, 67 function (in Erlang), 388 Haskell, 309 receive expression (in Erlang), 391 reduction rule semantics, 784 PDA (procedural data abstraction), 420 pencil, xviii Pentium III processor, 201, 471 performance cluster computing, 711 competitive concurrency, 254 constraint programming, 758 Cray-1 supercomputer, 175 declarative programming, 313 dictionary, 201 distributed stream, 724 lazy language, 289, 342 measuring, 167 memoization, 25, 315 mobile object, 724 monitor, 597 Mozart Programming System, 201, 379 personal computer, 175 price of concurrency, 339 record field access, 438 role of optimization, 177, 265, 302 role of parallelism, 237, 322 transitive closure, 471 word-of-mouth simulation, 486 permanent failure, 739 permutations, 2 persistence data structure, 149, 297 database, 654 Erlang, 387 transaction, 600 personal computer, 3, 252, 254, 289, 304 low-cost, 74, 175 pessimistic scheduling, 603 Phidani Software, 642 π calculus, xvii, 41, 54, 805 pipeline, 259 pixel, 556 placeholder dataflow variable, 86 future (in Multilisp), 336 GUI design, 686, 703 planning flight, 671 WARPLAN, 621 Plotkin, Gordon, 779 point resting, 338 synchronization, 333 two-dimensional space, 554 pointer, 76 content edge, 733 888 Index dependency, 459 dynamic typing, 106 garbage collection, 76 memory block, 480 resource, 480 state, 733 POLA (Principle of Least Authority), 209 polymorphism, 18, 106, 425, 462, 493 active objects, 429 ad-hoc, 429 apportioning responsibility, 425 example, 530 Haskell, 312 object-oriented programming, 490 port objects, 429 stream objects, 429 universal, 429 Ponsard, Christophe, 545 port (explicit state), 349, 719, 848 communication from inside encapsulated search, 673 distributed semantics, 383 Port.sendRecv operation, 673 portal, 476 postcondition, 441, 521 potential function, 175 precondition, 441, 521 predicate calculus, 633 preemption, 252 preprocessor, 318 DCG (in Prolog), 649 design patterns, 536 extended DCG (in Prolog), 140 fallacy of, 318 presentation model (in GUI), 695 principle abstraction, 410 avoid changing interfaces, 458 avoid premature optimization, 177, 452 balance planning and refactoring, 452 centralized first, distributed later, 745 class is final by default, 492 compartmentalize responsibility, 425, 451 concentrate explicit state, 412 creative extension, xiv, 844 decisions at right level, 460 declarative concurrency, 242, 281 document component interfaces, 451 documented violations, 460 eager default, lazy declared, 330 encapsulate design decisions, 458 enriching control (in logic programming), 640 error confinement, 90 “everything should be an object”, 542 exploit data abstraction uniformity, 543 form mirrors content, 544 freely exchange knowledge, 451 function structure follows type structure, 135 functional abstraction, 4 last call optimization, 72 layered language design, 850 least authority (POLA), 209 least expressiveness, 323 least privilege, 209 minimize dependencies, 387, 459 minimize indirections, 459 model independence, 457 more is not better or worse, just different, xx Mozart design rules, xxvi natural selection, 451, 462 need to know, 209 objects over ADTs, 490 pay only on use, 620 predictable dependencies, 460 run time is all there is, 504, 690 separation of concerns, 567 stateful component with declara- Index 889 tive behavior, 417 substitution property, 518, 521, 523 syntax stability, 643 system decomposition, 210 type first, 137 use data abstraction everywhere, 489, 543 working software keeps working, 59, 459, 722 private scope, 507, 508 C++ and Java sense, 508 Smalltalk and Oz sense, 507 probability exponential distribution, 475 Gaussian distribution, 476 normal distribution, 476 uniform distribution, 474 unique name generation, 207 problem cryptarithmetic, 755, 776 digital logic satisfiability, 176 Flavius Josephus, 558–561 flight planning, 671 grocery puzzle, 774 halting, 209, 681 Hamming, 293, 342 intractable, 176 library scheduler, 672 making change, 775 n-queens, 629 NP-complete, 176 palindrome product, 628, 757 Send-More-Money, 755, 776 undecidable, 209 zebra puzzle, 774 proc statement, 65, 792 procedure as component, 412 basic operations, 55 external reference, 65 importance, 54 order, 177 tail-recursive, 72 procedure value (closure), 65, 178, 792 anonymous, 53 common limitation, 179, 552 distributed lexical scoping, 722 encoding as an object, 540 higher-order programming, 177 relation to inner class, 552 process concurrent calculus, 54 concurrent program design, 364 CSP, 619 distributed system, 707 Erlang, 350, 386, 389 large program design, 450 operating system, 255 producer and consumer, 724 run-time error, 96 small program design, 218 processor, 237 cluster computing, 711 dataflow machine, 337, 469 parallel functional programming, 331 shared-memory multiprocessor, 710 producer, 257 profiling, 177, 452 program design, see software development program point, 444, 606 programming, xv, 1 accumulator, 139 component-based, 412 concurrent, 573 constraint, 44, 274, 577, 663 data-centered, 576 declarative, 29, 406 descriptive, 115 need for algorithms, 116 programmable, 115 Erlang, 388 flow-based, 257 functional, 406 890 Index future developments, 461 good style, xxi Haskell, 309 higher-order, 113, 123, 177–194 introduction, 13 relation to object-oriented, 538 imperative, 29, 406 Java, 552, 615 kernel language approach, xvi logic, 44, 101, 142, 406, 632 multi-agent, 412, 576 multiparadigm, xiv, xxvi event manager, 566 nonalgorithmic, 622 object-based, 19, 538 object-oriented (OOP), 19, 413, 489 open, 105, 202 paradigm, xiii, xvi, 29, see computation model Prolog, 663 real-time, 304 relational, 621 stateful, 29 stateless, 29 synchronous, 266 programming model, xiii, 29 Prolog, 660–671 Aquarius, 140, 661 Parma, 661 SICStus, 190, 663 state threads package, 190 proof engineering, 117 proof rule, 444 propagate-and-search, 629, 750 propagator, 752, 760 property liveness, 602 object, 497 safety, 602 propositional logic, 632 protected scope, 508 C++ sense, 509 Java sense, 567 protection boundary, 202 protector, 325 protocol, 353 by-need, 282 communication, 715 consistency, 712 DHCP (Dynamic Host Connection Protocol), 207 distributed binding, 733 distributed unification, 733 eager copy, 734 eager immediate copy, 734 interaction (in GUI), 682 invalidation, 733 IP (Internet Protocol), 206 lazy copy, 733 meta-object, 516 mobile state, 733 negotiation, 376 short-circuit, 559 stationary state, 733 TCP (Transmission Control Protocol), 712, 740 timer, 368 Prototyper tool, 689 pseudorandom numbers, 473 Psion Series 3 palmtop computer, 378 public scope, 507 pure object-oriented language, 543 QTk, 213, 680, 729 interactive use, 214, 684 Prototyper, 689 use in application, 225 quadratic equation, 179 quantifier, 441, 445, 633, 645 existential (in Prolog), 671 quantum (in thread scheduling), 252 query database, 655 logic programming, 634 queue, 145 amortized ephemeral, 147 amortized persistent, 298 Index 891 breadth-first traversal, 156 concurrent, 379, 583 nonblocking delete, 598 priority, 605, 614 worst-case ephemeral, 147 worst-case persistent, 299 race condition, 20, 234 raise statement, 93, 801 random number generation, 472 rational tree, 760 Raymond, Eric, 462 reachable memory, 74 ReadOnly operation, 799 real-time computing garbage collection, 76 hard, 174, 253, 254, 304 soft, 304 reasoning algebraic, 111, 116, 323 atomic action, 581 causal, 353, 575 lift control system, 375 logical, xix, 111, 632 message-passing concurrent model, 352 shared-shate concurrent model, 324 stateful model, 324, 440 receive asynchronous, 332 nonblocking, 333 synchronous, 332 receive expression (in Erlang), 391 recomputation, 761, 776 record, 19, 52, 825 adjoin, 827 basic operations, 54, 826 dynamic creation, 165, 549, 695 importance, 53 type, 438 usage trade-offs, 438 recurrence equation, 167 recursion, 3, 113, 124 direct, 113 indirect, 113 mutual, 110 polymorphic, 309 programming with, 127 Prototyper tool, 690 tail recursion optimization, 72 red cut (in Prolog), 670 Red Hat Corporation, xxvi, 201, 471 reduction order, 330–332 applicative, 330 normal, 330 reduction rule, 784 reengineering, 522 refactoring, 452 reference, 714 referential transparency, 113 reflection, 515 region (in OPI), 815 register abstract machine, 56 forwarding, 621 memory management, 74 registration action procedures (in GUI), 683 display refresh (FlexClock), 700 distributed binding, 737 finalization, 481 relation, 655 relative error, 120 reliability, 711 rendezvous, 619 replicator, 326 research project, xxiv resolution deadlock, 605 logic programming, 635, 640, 662 SLDNF, 662 video display, 321 resource distributed component, 746 distributed system, 729 external, 77, 480 file descriptor, 293 892 Index localized, 709 producer/consumer pipeline, 261 use of laziness, 289 responsibility atomicity and consistency (in transaction), 600 compartmentalize (in a team), 451 coroutine (avoiding starvation), 275 design by contract, 521 distributed memory management, 738 dynamic typing, 493 failure confinement, 245 memory management, 76 role of polymorphism, 425 type inference, 137 resting point, 338 restriction (environment), 62 retract/1 operation (in Prolog), 662 return (in for loop), 190 Reuter, Andreas, 582, 600 Reynolds, John C., 419 right, see name Rinard, Martin C., 338 RISC (Reduced Instruction Set Computer) microprocessor, 621 RMI (remote method invocation), 354, 709, 724, 725 root variable, 763 Round operation, 822 RPC (remote procedure call), 354, 709 rubber band, 251 runic inscription, 779 Runnable interface (in Java), 616 s-expression, 650 Sacks, Oliver, 405 safety, 602 Saint-Exupéry, Antoine de, 111 Santayana, George, 694 Saraswat, Vijay A., 338, 662, 808 scalability compilation, 458 multiprocessor, 710 program development, 105 weighted reference counting, 737 scalar product (constraint), 775 scheduler Delay operation, 304 deterministic, 253 lift control system, 366 nondeterministic, 253 randomness, 473 resource allocation, 672 round-robin, 252, 256 thread, 239, 252 transaction, 603 Schulte, Christian, xxvi science, xv, xviii scientific method, xvii scope, 56, 507 attribute, 510 dynamic, 59 lexical, 57, 59, 64, 508, 539 absence in Prolog, 661 distributed, 722 hiding, 221, 411, 423, 442, 483, 495, 549 substitution, 803 private, 507, 508 protected, 508 public, 507 static, see lexical user-defined, 508 search aggregate, 670 all-solutions, 626 binary, 151 branch-and-bound, 772 breadth-first, 644 communication from inside encapsulated search, 673 constraint programming, 274 contribution of AKL, 809 danger, 639 Index 893 database query, 657 depth-first, 622, 644 deterministic, 621 encapsulated, 625 generate-and-test, 629, 758 iterative deepening, 644 linear, 197 logic programming, 661 n-queens problem, 629 one-solution, 626 overuse, xxi propagate-and-search, 629, 750 pruning, 662 relational computation model, 623 relational programming, 621 saturation, 772 search space, 622 search strategy, 761 search tree, 624 security abstract data type, 201–210 application, 744 atom vs. name, 508 capability, 208 data abstraction, 419–435 distributed resources, 731 distributed system, 743 engineering, 744 hardware, 744 human society, 208 implementation, 744 kernel language concepts, 847 language, 208, 744 linguistic abstraction, 39 mechanism, 208 open distribution, 711 policy, 208 right, 791, 847 static typing, 106 threat model, 744 self clone, 517 delegation, 511 dynamic binding, 505 forwarding, 511 Java, 553 this notation, 551 self (in Erlang), 390 semantic stack, 62 runnable, 62 suspended, 62 terminated, 62 semantics, 31 abstract machine, 56–78, 92–94, 239–241, 282–283, 348–349, 416–417 axiomatic, 38, 440–450, 632 by-need trigger, 282 cell, 416 common abstractions, 808 denotational, 38 exceptions, 92 interleaving, 780 kernel language, see abstract machine kernel language approach, 38 logical, 38, 631–641 monitor (in Java), 592 operational, 38, 60, 635, 779–811 port, 348, 383 secure types, 203 semantic statement, 61 SOS (structural operational semantics), 779 thread, 239 Send operation, 349 slot-reserving semantics, 384 send asynchronous, 332 latency, 263 nonblocking, 333 synchronous, 332 Send-More-Money problem, 755, 776 separation of concerns, 567 sequential logic, 269 serializability, 600 serialization, 709 894 Index serializer, 325 set comprehension, 301 setof/3 operation (in Prolog), 626, 666, 670 Shakespeare, William, 815 shared-state concurrency, see atomic action, see lock, see monitor, see transaction sharing, 418 Browser tool, 102, 829 distributed state, 720 distributed value, 716 thread, 378 short-circuit concurrent composition, 277 Flavius Josephus problem, 559 transitive closure, 464 Show operation, 340 side effect, 411 declarative, 288 signal operation (in monitor), 592 signature (of procedure), 129 simulation components, 412 digital logic, 266–272 inadequacy of declarative model, 173 Internet, 412 multi-agent, 412 slow network, 578 small world, 486 word-of-mouth, 476 Simurgh, 707 single-assignment store, 42–49, 60, 781 importance, 43 singularity, 176 sink (consumer), 259 64-bit address, 78 64-bit word, 74, 175, 820 skip statement, 62, 785 SLDNF resolution, 662 small world graph, 461 simulation, 486 Smolka, Gert, xxvi snapshot (of state), 437, 718 software design, see design methodology, see language design software development, 218, 450 bottom-up, 451 compositional, 453 concurrent components, 362 distributed programming, 745 evolutionary, 451 extreme programming, 452 framework, 492 IID (Iterative and Incremental), 451 importance of names, 508 in the large, 450 in the small, 218 incremental, 451 interactive interface, 87 iterative, 451 middle-out, 451 stepwise refinement, 465, 604 test-driven, 452 top-down, 8, 451 software engineering, 450 component as unit of deployment, 221 concurrency, 233 distributed lexical scoping, 722 further reading, 462 informatics curriculum, xxii lexical scoping, 59 software rot, 459 Solaris operating system, xxvi, xxix Solve operation, 626, 773 SolveAll operation, 626 SolveOne operation, 626 Sort operation, 670, 829 SOS (structural operational semantics), 779 source (producer), 259 source code, 221 interactive, 815 Index 895 million line, xvi, 36, 387, 457, 458 nonexistent, 492 preprocessor input, 318 reengineering, 522 set of functors, 285 textual scope, 64 variable name, 44 space, see computation space, see memory space leak, see memory leak specification, 410 component, 461 specification language, 116 speculative execution (in nonstrict language), 331 stack declarative object, 423 depth-first traversal, 156 memory management, 74 open declarative, 195, 421 proving it correct, 442 secure declarative bundled, 423 secure declarative unbundled, 205, 422 secure stateful bundled, 424 secure stateful unbundled, 424 semantic, 61 stateful concurrent, 578 standalone application, 222 declare not allowed, 87 Java, 555 uncaught exception, 93 starvation, 275 wait set implementation, 597 state cell (mutable variable), 414 declarative, 408 explicit, 16, 409 implicit, 408 interaction with call by name, 485 lazy execution, 481 lazy language, 331 memory management, 77 modularity property, 315 nonstrict language, 331 port (communication channel), 347 reasoning with, 38, 440 revocable capability, 434 threading, 139 transformation, 133 state transition diagram, 353, 368 component design, 364 floor component, 369 lift component, 371 lift controller component, 369 transaction, 607 stateless (declarative programming), 111 statement case, 67, 790 catch (clause in try), 94 choice, 623, 772 conc, 278 declare, 2, 87 fail, 623 finally (clause in try), 94 for, 188 fun, 84 functor, 223 gate, 272 if, 66, 790 local, 56, 63, 786 lock, 22, 583 proc, 65, 792 raise, 93, 801 skip, 62, 785 thread, 241, 785 try, 92, 799 break, 486 compound, 117 compound (in Java), 552 declarative kernel language, 49 interactive, 87 procedure application, 66 sequential composition, 63, 785 suspendable, 65 896 Index value creation, 63 variable-variable binding, 63 static binding, 506 linking, 222 scope, see scope, lexical typing, 51, 104–106 stdin (standard input), 229, 553 stdout (standard output), 553 Steiner, Jennifer G., 334 Stirling’s formula for factorial, 618 storage manager, 325 store, 781 equivalence, 785 mutable (for cells), 416 mutable (for ports), 348 need, 780, 795 predicate, 781 read-only, 206, 798 single-assignment, 42–49, 60, 99, 235, 781 trigger, 282, 795 value, 43 stream, 795 deterministic, 257 Java, 553 merger, 395 producer/consumer, 257 usage trade-offs, 439 strict . . . , see eager . . . strict two-phase locking, 604 strictness analysis, 289, 310, 342 string, 53, 830 virtual, 211, 831 StringToAtom operation, 824 structure compiler, 162 compositional, 461 difference, 141 distribution, 255 effect of concurrency, 252 grammar, 32 hierarchical, 453 interpreter, 653 noncompositional, 461 program, 219, 220 structure equality, 103, 418, 723 substitution, 126, 803 substitution property, 518, 521, 523 subtype basic types, 52 class hierarchy, 518 Sun Microsystems, xxvi, 462 superclass, 503, 513, 556 supercomputer, 175 supply-driven execution, see eager execution suspension Delay operation, 305 due to program error, 48, 89 thread, 239, 276 Sussman, Gerald Jay, 42 Sussman, Julie, 42 Symbian Ltd., 378 symbolic link, 459 synchronization, 333–337 clock, 308 dataflow, 790 synchronized keyword, 593, 616 synchronous communication, 332 active object variant, 562 component interaction, 456 CSP, 619 dependency, 387 error reporting, 360 failure detection, 400, 739 fault confinement, 745 receive, 332 send, 332 synchronous programming, 266 syntactic sugar, 40, 79–84 dynamic record creation, 165 local statement, 40 state transition diagram, 369 syntax, 31 convention for examples, xxix language, 31 nestable constructs (in Oz), 833 Index 897 nestable declarations (in Oz), 833 Oz language, 833 Oz lexical, 839 Prolog, 663 term (in Oz), 833 synthesized argument, 161 system exception, 96 Szyperski, Clemens, 462 tail call optimization, 72 Tanenbaum, Andrew S., 334 task (in concurrency), 780 tautology, 632 TCP (Transmission Control Protocol), 712, 740 technology, xv dangers of concurrency, 21 history of computing, 176 magic, 314 molecular computing, 176 Prolog implementation, 661 reengineering, 522 singularity, 176 software component, 462 synchronous digital, 267 transition to 64-bit, 78 Tel, Gerard, 353 tell operation, 782, 787 temporal logic, 603 temporary failure, 739 term Erlang, 391 Oz, 833 Prolog, 664 termination detection, 276, 382 ping-pong example, 305 failure in declarative program, 245 partial, 243, 338, 804 proof, 449 total, 804 test-driven development, 452 testing declarative programs, 111, 407 dynamic typing, 105 programming in the small, 219 stateful programs, 407 text file, 210 Thalys high-speed train, 382 theorem binomial, 4 Church-Rosser, 331 Gödel’s completeness, 634 Gödel’s incompleteness, 634 halting problem, 681 theorem prover, 117, 634, 662 Therac-25 scandal, 21 thinking machine, 621 third-party independence, 335 32-bit address, 78 32-bit word, 74, 174 this, see self Thompson, D’Arcy Wentworth, 405 thread, 846 declarative model, 233 hanging, 399 interactive interface, 89 introduction, 15 Java, 615 monotonicity property, 239, 781, 782 priority, 253 ready, 239 runnable, 239 suspended, 239 synchronization, 333 thread statement, 241, 785 Thread class (in Java), 616 throughput, 263 thunk, 432 ticket, 480, 714 Connection module, 715 ticking, 307 time complexity, 11 time slice, 252–254 duration, 254 898 Index time-lease mechanism, 480, 734, 738 time-out, 740 Erlang, 391–394 system design, 460 timer protocol, 368 timestamp, 207, 602 timing measurement active object, 379 memory consumption, 173 palindrome product (constraint version), 758 palindrome product (naive version), 629 transitive closure, 471 word frequency, 201 token equality, 418, 714, 723 token passing, 579, 588, 591, 721 token syntax (of Oz), 833 tokenizer, 32, 162 top-down software development, 8, 451 total termination, 804 trade-off asynchronous communication vs. fault confinement, 745 compilation time vs. execution efficiency, 457 compositional vs. noncompositional design, 461 dynamic vs. static scoping, 58 dynamic vs. static typing, 104 explicit state vs. implicit state, 315, 409 expressiveness vs. execution efficiency, 116 expressiveness vs. manipulability, 681 functional decomposition vs. type decomposition, 542 helper procedure placement, 120 indexed collections, 435 inheritance vs. component composition, 462, 492 kernel language design, 844 language design, 811 lazy vs. eager execution, 329 memory use vs. execution speed, 177 names vs. atoms, 510 nonstrictness vs. explicit state, 331, 344 objects vs.

Data Structures & Algorithms Interview Questions You'll Most Likely Be Asked by Vibrant Publishers

NP-complete, sorting algorithm, traveling salesman

Answer: A greedy algorithm is any algorithm that makes the local optimal choice at each stage with the hope of finding the global optimum. A classical problem which can be solved using a greedy strategy is the traveling salesman problem. Another problems that can be solved using greedy algorithms are the graph coloring problem and all the NP-complete problems. 164: Which are the pillars of a greedy algorithm? Answer: In general, greedy algorithms have five pillars: a) a candidate set, from which a solution is created b) a selection function, which chooses the best candidate to be added to the solution c) a feasibility function, that is used to determine if a candidate can be used to contribute to a solution d) an objective function, which assigns a value to a solution, or a partial solution e) a solution function, which will indicate when we have discovered a complete solution 165: What is a backtracking algorithm?

Write Great Code, Volume 2 by Randall Hyde

complexity theory, Donald Knuth, Free Software Foundation, G4S, locality of reference, NP-complete, premature optimization

However, the compiler must also be capable of producing an executable result in a reasonable amount of time. The optimization process is an example of what complexity theory calls an NP-complete problem. These are problems that are, as far as we know, intractable. That is, a guaranteed correct result cannot be produced (for example, an optimal version of a program) without computing all possibilities and choosing the best result from those possibilities. Unfortunately, the time generally required to solve an NP-complete problem increases exponentially with the size of the input, which in the case of compiler optimization means roughly the number of lines of source code.

…

Natural offsets in an activation record, 16.5.2 Assigning Offsets to Local Variables Nested procedures, 8.5.3 Storage Allocation for Intermediate Variables new (memory allocation), 8.1.4 The Stack Section, 8.3.2 Pseudo-Static Binding and Automatic Variables, 8.3.3 Dynamic Binding and Dynamic Variables, 11.2 Pointer Implementation in High-Level Languages, 11.2 Pointer Implementation in High-Level Languages function, 8.3.3 Dynamic Binding and Dynamic Variables, 11.2 Pointer Implementation in High-Level Languages operator (C++ or Pascal), 8.1.4 The Stack Section next statement, 14.3 The goto Statement NIL, 14.5.3 Forcing Short-Circuit Boolean Evaluation in an if Statement Nodes in a call tree, 16.1.2 Other Sources of Overhead Non-numeric constants, 7.4 Manifest Constants Versus Read-Only Memory Objects Nonportable optimizations, 6.1 Background Nonscalar function return results, 16.6.2 Pass-by-Reference NOT operator, 15.2 The repeat..until (do..until/do..while) Loop NP-complete problems, 5.4.4 Optimization NULL pointer references, 8.1 Runtime Memory Organization NumberOfLinenumbers field in a COFF file, 5.6.3 COFF Section Headers NumberOfRelocations field in a COFF file, 5.6.3 COFF Section Headers NumberOfSections field in a COFF file, 5.6.1 The COFF File Header, 5.6.2 The COFF Optional Header Numeric constants, 3.4 Literal Constants O objdump, 5.8.4 Section Alignment and Library Modules, 6.3.1.3 The dumpbin.exe /headers Command-Line Option, 6.3.1.6 Other dumpbin.exe Command-Line Options, 6.3.2 The FSF/GNU objdump.exe Utility command-line options, 6.3.1.6 Other dumpbin.exe Command-Line Options utility, 5.8.4 Section Alignment and Library Modules, 6.3.1.3 The dumpbin.exe /headers Command-Line Option for GNU/Gas/GCC code, 6.3.1.3 The dumpbin.exe /headers Command-Line Option Object code files, Compiler Operation and Code Generation Object files, 5.4.4.5 Controlling Compiler Optimization, 5.5.2 Emitting Assembly Language as Compiler Output, 5.6.7 Learning More About Object File Formats, 5.7.1 Pages, Segments, and File Size as compiler output, 5.5.2 Emitting Assembly Language as Compiler Output formats, 5.6.7 Learning More About Object File Formats sections and memory consumption, 5.7.1 Pages, Segments, and File Size Object-oriented programs, overgeneralization in, 12.8.7 Classes, Objects, and Performance Objects, 12.7 Namespaces One-address machines, 13.1.2 Accumulator-Based Machines Operand sizes in assembly language, 3.8 Specifying Operand Sizes in Assembly Language, 3.8.1 Type Coercion in HLA, 4.9 The Minimal Instruction Set ambiguity (80x86), 3.8.1 Type Coercion in HLA on the PowerPC, 4.9 The Minimal Instruction Set operating system.

…

, 80x86 Assembly for the HLL Programmer, 3.4 Literal Constants, 3.4.3.2 Hexadecimal Literal Constants in Gas, 3.4.4.2 Character and String Literal Constants in Gas, 3.4.4.2 Character and String Literal Constants in Gas, 3.4.5 Floating-Point Literal Constants, 3.5.2 Manifest Constants in Gas, 3.5.2 Manifest Constants in Gas, 3.5.2 Manifest Constants in Gas, 3.6.1.1 Register Access in HLA, 3.6.1.3 Register Access in MASM and TASM, 3.6.2 Immediate Addressing Mode, 3.6.2 Immediate Addressing Mode, 3.6.4 Register Indirect Addressing Mode, 3.6.5.2 Indexed Addressing Mode in MASM and TASM, 3.6.6.1 Scaled-Indexed Addressing in HLA, 3.7.2 Data Declarations in MASM and TASM, 3.7.2 Data Declarations in MASM and TASM, 3.7.2 Data Declarations in MASM and TASM, 3.7.3 Data Declarations in Gas, 3.7.3 Data Declarations in Gas, 3.7.3.1 Accessing Byte Variables in Assembly Language, 3.8 Specifying Operand Sizes in Assembly Language, 3.8.1 Type Coercion in HLA, 6.2.1 Assembly Output from GNU and Borland Compilers, 6.2.3.2 Borland C++ Assembly Language Output, 8.5 Variable Addresses and High-level Languages = operator, 3.5.2 Manifest Constants in Gas binary constants, 3.4 Literal Constants character literal constants, 3.4.4.2 Character and String Literal Constants in Gas compatible assembly output from Borland C++, 6.2.3.2 Borland C++ Assembly Language Output constant declarations, 3.5.2 Manifest Constants in Gas data declarations, 3.7.2 Data Declarations in MASM and TASM db declarations, 3.7.2 Data Declarations in MASM and TASM dd/dword declarations, 3.7.3.1 Accessing Byte Variables in Assembly Language direct addressing mode, 3.6.2 Immediate Addressing Mode displacement-only addressing mode, 3.6.2 Immediate Addressing Mode, 8.5 Variable Addresses and High-level Languages dw declaration, 3.7.3 Data Declarations in Gas equ directive, 3.5.2 Manifest Constants in Gas floating-point literal constants, 3.4.5 Floating-Point Literal Constants hexadecimal literal constants, 3.4.3.2 Hexadecimal Literal Constants in Gas indexed addressing mode, 3.6.5.2 Indexed Addressing Mode in MASM and TASM initialized data, 3.7.2 Data Declarations in MASM and TASM mov instruction, 3.6.1.1 Register Access in HLA operand sizes, 3.8 Specifying Operand Sizes in Assembly Language register indirect addressing mode, 3.6.4 Register Indirect Addressing Mode register names, 3.6.1.3 Register Access in MASM and TASM scaled-indexed addressing modes, 3.6.6.1 Scaled-Indexed Addressing in HLA string literal constants, 3.4.4.2 Character and String Literal Constants in Gas type coercion, 3.8.1 Type Coercion in HLA word declaration, 3.7.3 Data Declarations in Gas TBL register (PowerPC), 4.3.3.3 XER Register TBU register (PowerPC), 4.3.3.3 XER Register TByte data (80x86), 3.7 Declaring Data in Assembly Language Tested code, 1.8 Characteristics of Great Code Text sections in an executable file, 5.7 Executable File Formats Textual substitution for parameters, 16.3 Macros and Inline Functions text_start field in a COFF file, 5.6.2 The COFF Optional Header Thread-safe code, 8.3.2 Pseudo-Static Binding and Automatic Variables Three-address architectures, 13.1.5 Three-Address Architectures Three-dimensional array access, 9.1.5.5 Accessing Elements of a Multidimensional Array Time Base facility (TBR) registers (PowerPC), 4.3 Basic PowerPC Architecture Time Base registers (TBL and TBU) (PowerPC), 4.3.3.3 XER Register Time required to optimize a program (NP-Completeness), 5.4.4 Optimization Time/space trade-off for macros, 16.3 Macros and Inline Functions TimeDateStamp (Windows COFF header field), 5.6.1 The COFF File Header Tokens, Compiler Operation and Code Generation, Compiler Operation and Code Generation, 5.4.1 Lexical Analysis and Tokens, 5.4.1 Lexical Analysis and Tokens, 5.4.1 Lexical Analysis and Tokens, 5.4.1 Lexical Analysis and Tokens attributes, 5.4.1 Lexical Analysis and Tokens composition, 5.4.1 Lexical Analysis and Tokens in a source file, Compiler Operation and Code Generation representing a source file, Compiler Operation and Code Generation streams, 5.4.1 Lexical Analysis and Tokens Top-of-stack, 13.1.1.1 Basic Stack Machine Organization, 13.1.1.3 Popping Data from a Stack Tracking changes to variables through a basic block, 5.4.4.3 Basic Blocks, Reducible Code, and Optimization Tracking memory use in a heap manager, 11.7 The OS and Memory Allocation Transfer of control at the machine level, Control Structures and Programmatic Decisions Translation from source code to machine code, 5.3.3 Compilers True, 7.6 Boolean Constants tsize field in a COFF file, 5.6.2 The COFF Optional Header Tuples, 12.1 Records Turbo Assembler.

Toast by Stross, Charles

anthropic principle, Buckminster Fuller, cosmological principle, dark matter, disinformation, double helix, Ernest Rutherford, Extropian, Fairchild Semiconductor, flag carrier, Francis Fukuyama: the end of history, Free Software Foundation, Future Shock, Gary Kildall, glass ceiling, gravity well, Great Leap Forward, Hans Moravec, Higgs boson, hydroponic farming, It's morning again in America, junk bonds, Khyber Pass, launch on warning, Mars Rover, Mikhail Gorbachev, military-industrial complex, Neil Armstrong, NP-complete, oil shale / tar sands, peak oil, performance metric, phenotype, plutocrats, punch-card reader, Recombinant DNA, Ronald Reagan, Silicon Valley, slashdot, speech recognition, strong AI, traveling salesman, Turing test, urban renewal, Vernor Vinge, Whole Earth Review, Y2K

Over on the other side of the office John’s terminal beeped, notification of incoming mail. A moment later my own workstation bonged. “Hey, Geoff! Get a load of this!” I carried on screwing the card back into its chassis. John is not a priority interrupt. “Someone’s come up with a proof that NP-complete problems lie in P! There’s a posting in comp.risks saying they’ve used it to find an O*(n2 ) solution to the traveling salesman problem, and it scales! Looks like April First has come early this year, doesn’t it?” I dropped the PC’s lid on the floor hastily and sat down at my workstation. Another cubed-sphere hypothesis, another flame war in the math newsgroups—or something more serious?

…

It exports confidentiality, delay-line buffers, fine wines, and dissidents. In other words, it’s the last place a futures trader specializing in spread option trades that leverage developments in the artificial intelligence market—someone like me—would normally be seen dead in. On the other hand . . . As an accountant specializing in Monte Carlo solutions to NP-complete low-knowledge systems I am naturally of interest to the Queen, who made me an offer I would have considered long and hard at the best of times; in my circumstances back on Dordogne—exposed to risk, to say the least—I could hardly consider refusing her invitation. Many technologies are banned from the system, in an attempt to reduce the vulnerability of the monarchy to algorithmic complexity attacks.

Mining the Social Web: Finding Needles in the Social Haystack by Matthew A. Russell

Andy Rubin, business logic, Climategate, cloud computing, crowdsourcing, data science, en.wikipedia.org, fault tolerance, Firefox, folksonomy, full text search, Georg Cantor, Google Earth, information retrieval, machine readable, Mark Zuckerberg, natural language processing, NP-complete, power law, Saturday Night Live, semantic web, Silicon Valley, slashdot, social graph, social web, sparse data, statistical model, Steve Jobs, supply-chain management, text mining, traveling salesman, Turing test, web application

The maximum clique is also a maximal clique in that it isn’t a subgraph of any other clique. However, various other maximal cliques often exist in graphs and need not necessarily share any nodes with the maximum clique. Figure 4-2, for example, illustrates a maximum clique of size 4, but there are several other maximal cliques of size 3 in the graph as well. Finding cliques is an NP-complete problem (implying an exponential runtime), but NetworkX does provide the find_cliques method, which delivers a solid implementation that takes care of the heavy lifting. Just be advised that it might take a long time to run as graphs get beyond a reasonably small size. Figure 4-2. An example graph containing a maximum clique of size 4 Example 4-11 could be modified in any number of ways to compute interesting things, so long as you’ve first harvested the necessary friendship information.

…

Using NetworkX to find cliques in graphs (friends_followers__clique_analysis.py) # -*- coding: utf-8 -*- import sys import json import networkx as nx G = sys.argv[1] g = nx.read_gpickle(G) # Finding cliques is a hard problem, so this could # take awhile for large graphs. # See http://en.wikipedia.org/wiki/NP-complete and # http://en.wikipedia.org/wiki/Clique_problem cliques = [c for c in nx.find_cliques(g)] num_cliques = len(cliques) clique_sizes = [len(c) for c in cliques] max_clique_size = max(clique_sizes) avg_clique_size = sum(clique_sizes) / num_cliques max_cliques = [c for c in cliques if len(c) == max_clique_size] num_max_cliques = len(max_cliques) max_clique_sets = [set(c) for c in max_cliques] people_in_every_max_clique = list(reduce(lambda x, y: x.intersection(y), max_clique_sets)) print 'Num cliques:', num_cliques print 'Avg clique size:', avg_clique_size print 'Max clique size:', max_clique_size print 'Num max cliques:', num_max_cliques print print 'People in all max cliques:' print json.dumps(people_in_every_max_clique, indent=4) print print 'Max cliques:' print json.dumps(max_cliques, indent=4) Sample output from the script follows for Tim O’Reilly’s 600+ friendships and reveals some interesting insights.

System Error by Rob Reich

"Friedman doctrine" OR "shareholder theory", "World Economic Forum" Davos, 2021 United States Capitol attack, A Declaration of the Independence of Cyberspace, Aaron Swartz, AI winter, Airbnb, airport security, Alan Greenspan, Albert Einstein, algorithmic bias, AlphaGo, AltaVista, artificial general intelligence, Automated Insights, autonomous vehicles, basic income, Ben Horowitz, Berlin Wall, Bernie Madoff, Big Tech, bitcoin, Blitzscaling, Cambridge Analytica, Cass Sunstein, clean water, cloud computing, computer vision, contact tracing, contact tracing app, coronavirus, corporate governance, COVID-19, creative destruction, CRISPR, crowdsourcing, data is the new oil, data science, decentralized internet, deep learning, deepfake, DeepMind, deplatforming, digital rights, disinformation, disruptive innovation, Donald Knuth, Donald Trump, driverless car, dual-use technology, Edward Snowden, Elon Musk, en.wikipedia.org, end-to-end encryption, Fairchild Semiconductor, fake news, Fall of the Berlin Wall, Filter Bubble, financial engineering, financial innovation, fulfillment center, future of work, gentrification, Geoffrey Hinton, George Floyd, gig economy, Goodhart's law, GPT-3, Hacker News, hockey-stick growth, income inequality, independent contractor, informal economy, information security, Jaron Lanier, Jeff Bezos, Jim Simons, jimmy wales, job automation, John Maynard Keynes: Economic Possibilities for our Grandchildren, John Maynard Keynes: technological unemployment, John Perry Barlow, Lean Startup, linear programming, Lyft, Marc Andreessen, Mark Zuckerberg, meta-analysis, minimum wage unemployment, Monkeys Reject Unequal Pay, move fast and break things, Myron Scholes, Network effects, Nick Bostrom, Northpointe / Correctional Offender Management Profiling for Alternative Sanctions, NP-complete, Oculus Rift, OpenAI, Panopticon Jeremy Bentham, Parler "social media", pattern recognition, personalized medicine, Peter Thiel, Philippa Foot, premature optimization, profit motive, quantitative hedge fund, race to the bottom, randomized controlled trial, recommendation engine, Renaissance Technologies, Richard Thaler, ride hailing / ride sharing, Ronald Reagan, Sam Altman, Sand Hill Road, scientific management, self-driving car, shareholder value, Sheryl Sandberg, Shoshana Zuboff, side project, Silicon Valley, Snapchat, social distancing, Social Responsibility of Business Is to Increase Its Profits, software is eating the world, spectrum auction, speech recognition, stem cell, Steve Jobs, Steven Levy, strong AI, superintelligent machines, surveillance capitalism, Susan Wojcicki, tech billionaire, tech worker, techlash, technoutopianism, Telecommunications Act of 1996, telemarketer, The Future of Employment, TikTok, Tim Cook: Apple, traveling salesman, Triangle Shirtwaist Factory, trolley problem, Turing test, two-sided market, Uber and Lyft, uber lyft, ultimatum game, union organizing, universal basic income, washing machines reduced drudgery, Watson beat the top human players on Jeopardy!, When a measure becomes a target, winner-take-all economy, Y Combinator, you are the product

Simpler methods take a “greedy” approach (“greedy algorithms” in computer speak) in which they simply select the next city to travel to based on the lowest cost from the current location before returning home. Though it might seem odd that solving the traveling salesperson problem would be worthy of a $1 million prize, its real power is that it’s surprisingly representative of a large class of problems, known as NP-complete problems, that underlies challenges as diverse as cryptography and DNA sequencing. Figure out an efficient algorithm to optimally solve TSP, and you will not only claim a $1 million prize but will also be able to break many encryption systems currently in use on the internet. The choices made when creating abstractions of the world have real-world consequences.

…

See data mining Mosaic browser, 30 multi-use technology, 16–17 Myron’s Law, 59 Nadella, Satya, 33–34 National Commission for the Protection of Human Subjects of Biomedical and Behavioral Research, 245–46 Nelson, Alondra, 261 net neutrality, 49, 61–62, 228 Netflix, 5–6 Netherlands Office of Technology Assessment (NOTA), 259 Netscape Communications, 30 Ng, Andrew, 171 Nichols, Tom, 68 Notice and Choice/Consent doctrine overview, 118–19, 120, 133–34, 137–40, 148 EPIC on companies’ privacy policies, 150–51 GDPR compared to, 144 Nozick, Robert, 167, 168 NP-complete problems, 13 nudges, 149 Nuremberg Code, 244–45 O’Neil, Cathy, 98 Obama, Barack, 200, 252 Obama administration’s consumer-privacy bill of rights, 146, 148 Oculus Rift VR goggles, 167 Office of Technology Assessment (OTA), 258–60, 261 Ohm, Paul, 130 OKRs (objectives and key results), 27–28, 31–34 On Liberty (Mill), 198–99 on-device intelligence, 134 Only the Paranoid Survive (Grove), 51 Open Government Partnership, xv Open Letter to the Internet (Berners-Lee), 126 OpenAI, 233–37 OpenSocial specification, 256 optimization mindset, 3–23 overview, xxix, 6 at Amazon, 4–5 corporate growth and, 33–37 deficiency of efficiency, 15–17 education of engineers, 10–15 focus on methods vs. goals, 15 measurable does not equal meaningful, 18–19 multiple valuable goals compete, 19–21 and multi-use technology, 16–17 at Netflix, 5–6 as orientation to life, 13–14 and profit motive leads to libertarianism, 52 and representational adequacy, 13 speculation on optimizing science, 22–23 of technologists, illustrated by Soylent, 9 technologists’ challenges when in government, 261 optimize, usage of term, 14 Ordóñez, Lisa, 34–37 Organisation for Economic Co-operation and Development (OECD), 174 Oversight Board of Facebook, 213–16 Oxford University, 174 Page, Larry, 27–28 Panopti-Cam, 124 panopticon, digital, 113–14, 121–26 “Panopticon” (Bentham), 121–22 parking tickets, social harm or social benefit, xix–xxi Perkins, Frances, 54, 55 personal computing industry, 26 personal ethics, xxix–xxx Plato, 65–66, 67, 75 politicians effect of regulations, or lack of, on digital tech, 53–59, 60–63 lobbying by big tech, 146–47, 253, 261 power of a newswire monopoly, 57 power of economists and political philosophers, 10 power through lobbying, 46, 47–49 stepping up if their jobs depend on it, 262–63 technical ignorance of, 71–72 See also winner-take-all, disruption vs. democracy politics, xxxii–xxxiii, 25, 52, 67, 75–76 Popper, Karl, xxxii–xxxiii, 75–76 Postal Service Act (1792), 3 poverty, escaping from, 170–71 prison panopticon, 123 privacy, 111–51 overview, 114–15 anonymization, 129–30 Apple’s privacy by design, 134–35 beyond GDPR, 145–47 consumer privacy, 125, 126 data mining vs., 84–87, 115–20 differential privacy, 130–33 digital blackout, 127–29 digital panopticon, 121–26 digital trustmediary, 149 effect of COVID-19 pandemic, 139 FTC regulation role, 150–51 GDPR data protection, 142–45 harm from lack of, 120, 124–25 and HIPAA, anonymization, 129–30 marketplace of different providers, 133–36 privacy paradox, 113–15, 137–40 protection as a benefit of society, 140–42 public support for regulations, 148 security vs., 71, 166 Stanford panel discussion on, 119–20 technology and biomedical research, 129–33 See also facial recognition technology private right of action in California, 147 procedural fairness, 92–93 professional ethics, xxx–xxxi, 244 ProPublica investigation of racism in Florida’s criminal court, 97 Public Access to Court Electronic Records (PACER), xxiii public health vs. factory farms, 20–21 Putin, Vladimir, 84 quantitative hedge funds using AI, 163–64 Rabois, Keith, 191–92 racial discrimination in machine-based recruiting system, 80–81 Rahwan, Iyad, 179 random “noise” in data, 131–32 randomized response survey design, 131–32 Rawls, John, 93–94 Reagan, Ronald, 258–59 Really Simple Syndication (RSS) specification, xxii recruiting system with gender bias, 81–82, 83 Reddit, xxii, 44 regret minimization framework, 30 regulations overview, 53 antitrust-based, 55–59, 227–28 based on OTA nonpartisan information, 258 constrain market dominance of big tech companies, 256–57 for creating healthy market competition, 229–30 government’s complicity in absence of, 59–63 matching tech sector innovation with appropriate regulatory structures, 261 medical research and education regulations, 244–51 policy-makers’ dilemma, 56–57 and politicians’ limited tech knowledge, 52–53 on tech start-ups, 45 technical ignorance of lawmakers, 71–72 technology companies lobby for autonomy, 46 when social consequences become intolerable, 55 Reich, Rob, xvi, 22–23 Renaissance Technologies, 163–64 representational adequacy, 13 Republic, The (Plato), 65–66 résumés and algorithmic decision-making, 82–87, 109 revenue optimization process, 43–45 Rhinehart, Rob, 7–9, 20 road safety, 154–55, 239 role of citizens in a democracy, xiv Romer, Paul M., 58–59, 176 Rush, Benjamin, 3 safety, 53–54, 55, 133–34, 154–55, 239 Sahami, Mehran, xv, 27, 38 Samuel, Arthur, 84, 156 San Bernardino, California, terrorist attack, 72, 134–35 Sanger, Larry, 195 Schatz, Brian, 240 Scholes, Myron, 59 search engine optimization (SEO), 196 Section 230, Communications Decency Act (CDA 230), 62, 221–23, 225 security, 20, 56, 71–72, 111–14, 116–17, 121–25, 128–29, 134–35, 141, 156, 166, 258 self-driving vehicles DARPA Grand Challenge, 153–54 effect on truck drivers and trucking industry, 175 human nature vs., 155–56 human pleasure from driving, 172 safety of, 154–55 in Silicon Valley, 186 society’s response to, 175 Sen, Amartya, 74, 172–73 separations regime, 229 September 11, 2001, terrorist attacks, 116 Sherman, John, 228 Sherman, Rob, 119–20 Shklar, Judith, 76 Siebel, Michael, 40 Sifton, Sam, 9 Silicon Valley, xiv, xxv–xxvi, 28, 40–41, 73 Silverberg, Nicole, 188 Simplex algorithm, 12 smart machines and humans, 153–86 overview, 160–65 autonomous weapons, 177–78 benefits for people whose jobs are changed or lost, 182–86 choice of human flourishing or greater productivity, 169 deep learning concept, 161–62 ethics and AI, 165–66 jobs lost and other costs of adjustment, 174–76 keeping humans in the loop, 178–82 livelihood destroying potential, 170–71 overcoming poverty to promote human flourishing, 170–71 value of freedom, 172–73 virtual reality, the experience machine, 167–69 Snowden, Edward, 116, 126, 139, 143–45 social and political ethics, xxxi–xxxiii Social Dilemma, The (documentary), 238–39 “Social Responsibility of Business Is to Increase Its Profits, The” (Friedman), 37–38 social safety nets, Europe and US compared, 185–86 social science, xv–xvii, xxvi, 137–40 Software Engineering Code of Ethics, 248 Solove, Daniel, 140 Soylent, 6–9, 20 Soylent Green (film), 7–8 Spliddit’s “provably fair solutions,” 88–89 Stanford University, Stanford, California overview, xiv, xv, xvi hate speech or hateful protected speech, 191–92 panel discussion on privacy concerns, 119–20 study of libertarian attitudes of tech leaders, 52 teaching computer science with social science and ethics, 251 VCs showcasing their new companies, 42–45 start-up accelerators, 44.

Mining of Massive Datasets by Jure Leskovec, Anand Rajaraman, Jeffrey David Ullman

cloud computing, crowdsourcing, en.wikipedia.org, first-price auction, G4S, information retrieval, John Snow's cholera map, Netflix Prize, NP-complete, PageRank, pattern recognition, power law, random walk, recommendation engine, second-price auction, sentiment analysis, social graph, statistical model, the long tail, web application

Interestingly, the technique for doing this search on a large graph involves finding large frequent itemsets, as was discussed in Chapter 6. 10.3.1Finding Cliques Our first thought about how we could find sets of nodes with many edges between them is to start by finding a large clique (a set of nodes with edges between any two of them). However, that task is not easy. Not only is finding maximal cliques NP-complete, but it is among the hardest of the NP-complete problems in the sense that even approximating the maximal clique is hard. Further, it is possible to have a set of nodes with almost all edges between them, and yet have only relatively small cliques. EXAMPLE 10.10Suppose our graph has nodes numbered 1, 2, . . . , n and there is an edge between two nodes i and j unless i and j have the same remainder when divided by k.

…

., 382 Newspaper articles, 109, 286, 296 Non-Euclidean distance, 238, see also Cosine distance, see also Edit distance, see also Hamming distance, see also Jaccard distance Non-Euclidean space, 252, 254 Norm, 87, 88 Normal distribution, 244 Normalization, 305, 307, 318 Normalized cut, 344 NP-complete problem, 338 Numerical feature, 416, 455 O’Callaghan, L., 265 Off-line algorithm, 270 Olston, C., 67 Omiecinski, E., 226 On-line advertising, see Advertising On-line algorithm, 16, 270 On-line learning, 421 On-line retailer, 194, 268, 292, 294 Open directory, 174, 422 OR-construction, 95 Orr, G.B., 458 Orthogonal vectors, 231, 389 Orthonormal matrix, 397, 402 Orthonormal vectors, 389, 393 Out-component, 159 Outlier, 230 Output, 54 Overfitting, 303, 319, 419, 420, 432, 456 Overlapping Communities, 350 Overture, 276 Own pages, 178 Paepcke, A., 122 Page, L., 154, 190 PageRank, 3, 15, 28, 29, 40, 154, 156, 168 Pairs, see Frequent pairs Palmer, C.R., 383 Pan, J.

The Debian Administrator's Handbook, Debian Wheezy From Discovery to Mastery by Raphaal Hertzog, Roland Mas

bash_history, Debian, distributed generation, do-ocracy, en.wikipedia.org, end-to-end encryption, failed state, Firefox, Free Software Foundation, GnuPG, Google Chrome, Jono Bacon, MITM: man-in-the-middle, Neal Stephenson, NP-complete, precautionary principle, QWERTY keyboard, RFC: Request For Comment, Richard Stallman, Skype, SpamAssassin, SQL injection, Valgrind, web application, zero day, Zimmermann PGP

On the other hand, the script identifying the families of related packages works hard to create them (this would be an NP-complete problem, for which, fortunately, we know some good heuristics). This is why we can manually interact with and guide this script by suggesting groups of packages, or imposing the inclusion of certain packages in a group, even if this temporarily breaks some dependencies. This functionality is accessible to the Release Managers and their assistants. Recall that an NP-complete problem is of an exponential algorithmic complexity according to the size of the data, here being the length of the code (the number of figures) and the elements involved.

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation by William J. Cook

Bletchley Park, complexity theory, computer age, Computer Numeric Control, financial engineering, four colour theorem, index card, John von Neumann, linear programming, NP-complete, P = NP, p-value, RAND corporation, Richard Feynman, traveling salesman, Turing machine

NorthHolland. 32–54. [11] Flood, M. 1954. Operations research and logistics. Proceedings of the First Ordnance Conference on Operations Research. Office of Ordnance Research, Durham, North Carolina. 3–32. [12] Garey, M. R., D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, California. [13] Gomory, R. E. 1966. The traveling salesman problem. Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems. IBM, White Plains, New York. 93–121. [14] Grötschel, M., O. Holland. 1991. Solution of large-scale symmetric travelling salesman problems.

The Art of Computer Programming by Donald Ervin Knuth

Abraham Wald, Brownian motion, Charles Babbage, complexity theory, correlation coefficient, Donald Knuth, Eratosthenes, G4S, Georg Cantor, information retrieval, Isaac Newton, iterative process, John von Neumann, Louis Pasteur, mandelbrot fractal, Menlo Park, NP-complete, P = NP, Paul Erdős, probability theory / Blaise Pascal / Pierre de Fermat, RAND corporation, random walk, sorting algorithm, Turing machine, Y2K

., bs are any addition chains, then J(]T djcubj) < r + 5 + ]T aj — 1 for any (r + 1) x E + 1) matrix of nonnegative integers dj. 41. [SICOMP 10 A981), 638-646.] The stated formula can be proved whenever A > 9m2. Since this is a polynomial in m, and since the problem of finding 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 chain for {ni,... ,nm}, when A is sufficiently large.] SECTION 4.6.4 1. Set y «— x2, then compute ((... (u2n+iy + U2n-i)y + • • ¦ )y + U\)x. 2. Replacing x in B) by the polynomial x + xo leads to the following procedure: Gl.

…

The tensor rank of an arbitrary m x n x 2 tensor in a suitably large field has been determined by Joseph Ja'Ja', SICOMP 8 A979), 443-462; JACM 27 A980), 822-830. See also his interesting discussion of commutative bilinear forms 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 scratched the surface of a very large subject in which many beautiful theories are emerging. Considerably more comprehensive treatments can be found in the books Computational Com- Complexity of Algebraic and Numeric Problems by A.

…

Normalization of divisors, 272-273, 282-283. Normalization of floating point numbers, 215-217, 227-228, 238, 248-249, 254, 616. Normand, Jean-Marie, 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, 403, 674. Number sentences, 605. Number system: A language for representing numbers. balanced binary, 213. balanced decimal, 211. balanced mixed-radix, 103, 293, 631. balanced ternary, 207-208, 209, 227, 283, 353. binary (radix 2), 195, 198-206, 209-213, 419, 461, 483. combinatorial, 209. complex, 205-206, 209-210, 292. decimal (= denary, radix ten), 197—199, 210, 320-326, 374. duodecimal (radix twelve), 199-200. factorial, 66, 209.

Algorithms in C++ Part 5: Graph Algorithms by Robert Sedgewick

Erdős number, functional programming, linear programming, linked data, NP-complete, reversible computing, search costs, sorting algorithm, traveling salesman

We have seen many examples of digraph-processing problems that are much more difficult to solve in the presence of cycles. Perhaps the most prominent example is the shortest-paths problem in weighted digraphs 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 equivalent to the standard maxflow problem. Proof: Again, we need only to show that the standard problem reduces to the acyclic problem. Given any network with V vertices and E edges, we construct a network with 2V +2 vertices and E +3V edges that is not just acyclic but has a simple structure.

…

D. E. Knuth, The Art of Computer Programming. Volume 1:Fundamental Algorithms, third edition, Addison-Wesley, 1997. J. R. Kruskal Jr., “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 networks and some generalizations,” Bell System Technical Journal, 36 (1957). R. E. Tarjan, “Depth-first search and linear graph algorithms,” SIAM Journal on Computing, 1, 2 (1972).

A Natural History of Beer by Rob DeSalle

agricultural Revolution, British Empire, CRISPR, double helix, Drosophila, Louis Pasteur, microbiome, NP-complete, phenotype, placebo effect, wikimedia commons

As a compromise, we tried rooting our tree with two relatively closely related beverages, gruit and wine. Next, as already mentioned, came the sheer computational difficulty that is involved in evaluating 10100 different trees. Computing the solutions for so many trees poses what mathematicians and computer scientists call an NP-complete problem: even though we know there is a finite solution to the problem, we don’t have the computing power to find it, so we must seek another road. In other words, with this many trees to examine we need to use shortcut methods that eliminate large swaths of those trees that will definitely not be part of the solution.

RDF Database Systems: Triples Storage and SPARQL Query Processing by Olivier Cure, Guillaume Blin

Amazon Web Services, bioinformatics, business intelligence, cloud computing, database schema, fault tolerance, folksonomy, full text search, functional programming, information retrieval, Internet Archive, Internet of things, linked data, machine readable, NP-complete, peer-to-peer, performance metric, power law, random walk, recommendation engine, RFID, semantic web, Silicon Valley, social intelligence, software as a service, SPARQL, sparse data, web application

These languages are also characterized by complexities for a set of selected reasoning problems. For example, with DLs like ALC (considered the Storage and Indexing of RDF Data first DL of interest due to its set of constructors) or SHIQ, the combined complexities of CQ answering are respectively Exptime-complete and 2-ExpTime-complete and NP-complete for data complexity. Besides these high complexities, some lightweight DLs have been identified with polynomial complexity for CQ answering. The DL-Lite family is one of them and it motivated the creation of the OWL2QL recommendation. The basic DL-Lite logic provides key conceptual modeling constructs like concept inclusion and disjointness, as well as domain and range constraints; other DL-Lite logics support functionality constraints, property inclusion and disjointness, and data types.

Advances in Financial Machine Learning by Marcos Lopez de Prado

algorithmic trading, Amazon Web Services, asset allocation, backtesting, behavioural economics, bioinformatics, Brownian motion, business process, Claude Shannon: information theory, cloud computing, complexity theory, correlation coefficient, correlation does not imply causation, data science, diversification, diversified portfolio, en.wikipedia.org, financial engineering, fixed income, Flash crash, G4S, Higgs boson, implied volatility, information asymmetry, latency arbitrage, margin call, market fragmentation, market microstructure, martingale, NP-complete, P = NP, p-value, paper trading, pattern recognition, performance metric, profit maximization, quantitative trading / quantitative finance, RAND corporation, random walk, risk free rate, risk-adjusted returns, risk/return, selection bias, Sharpe ratio, short selling, Silicon Valley, smart cities, smart meter, statistical arbitrage, statistical model, stochastic process, survivorship bias, transaction costs, traveling salesman

A solution will be found even if the covariance matrices are ill-conditioned, transaction cost functions are non-continuous, etc. The price we pay for this generality is that calculating the solution is extremely computationally intensive. Indeed, evaluating all trajectories is similar to the traveling-salesman problem. Digital computers are inadequate for this sort of NP-complete or NP-hard problems; however, quantum computers have the advantage of evaluating multiple solutions at once, thanks to the property of linear superposition. The approach presented in this chapter set the foundation for Rosenberg et al. [2016], which solved the optimal trading trajectory problem using a quantum annealer.

Atrocity Archives by Stross, Charles

airport security, anthropic principle, Berlin Wall, Bletchley Park, brain emulation, British Empire, Buckminster Fuller, defense in depth, disinformation, disintermediation, experimental subject, glass ceiling, haute cuisine, hypertext link, Khyber Pass, luminiferous ether, mandelbrot fractal, Menlo Park, MITM: man-in-the-middle, Neal Stephenson, NP-complete, PalmPilot, pneumatic tube, Snow Crash, Strategic Defense Initiative, the medium is the message, Y2K, yield curve

Anyway, the theorem has been rediscovered periodically ever since; it has also been suppressed efficiently, if a little bit less violently, because nobody wants it out in the open where Joe Random Cypherpunk can smear it across the Internet. The theorem is a hack on discrete number theory that simultaneously disproves the Church-Turing hypothesis (wave if you understood that) and worse, permits NP-complete problems to be converted into P-complete ones. This has several consequences, starting with screwing over most cryptography algorithms--translation: all your bank account are belong to us--and ending with the ability to computationally generate a Dho-Nha geometry curve in real time. This latter item is just slightly less dangerous than allowing nerds with laptops to wave a magic wand and turn them into hydrogen bombs at will.

Entangled Life: How Fungi Make Our Worlds, Change Our Minds & Shape Our Futures by Merlin Sheldrake

Anthropocene, Apollo 11, biofilm, buy low sell high, carbon footprint, CRISPR, crowdsourcing, cuban missile crisis, dark matter, deep learning, discovery of penicillin, Easter island, experimental subject, Fellow of the Royal Society, Isaac Newton, Kickstarter, late capitalism, low earth orbit, Mason jar, meta-analysis, microbiome, moral panic, NP-complete, phenotype, randomized controlled trial, Ronald Reagan, seminal paper, TED Talk, the built environment, Thomas Bayes, Thomas Malthus, traveling salesman, two and twenty

The neuroactive potential of the human gut microbiota in quality of life and depression. Nature Microbiology: 623–32. van Delft FC, Ipolitti G, Nicolau DV, Perumal A, Kašpar O, Kheireddine S, Wachsmann-Hogiu S, Nicolau DV. 2018. Something has to give: scaling combinatorial computing by biological agents exploring physical networks encoding NP-complete problems. Journal of the Royal Society Interface Focus 8: 20180034. van der Heijden MG. 2016. Underground networking. Science 352: 290–91. van der Heijden MG, Bardgett RD, Straalen NM. 2008. The unseen majority: soil microbes as drivers of plant diversity and productivity in terrestrial ecosystems.

Rationality: From AI to Zombies by Eliezer Yudkowsky

Albert Einstein, Alfred Russel Wallace, anthropic principle, anti-pattern, anti-work, antiwork, Arthur Eddington, artificial general intelligence, availability heuristic, backpropagation, Bayesian statistics, behavioural economics, Berlin Wall, Boeing 747, Build a better mousetrap, Cass Sunstein, cellular automata, Charles Babbage, cognitive bias, cognitive dissonance, correlation does not imply causation, cosmological constant, creative destruction, Daniel Kahneman / Amos Tversky, dematerialisation, different worldview, discovery of DNA, disinformation, Douglas Hofstadter, Drosophila, Eddington experiment, effective altruism, experimental subject, Extropian, friendly AI, fundamental attribution error, Great Leap Forward, Gödel, Escher, Bach, Hacker News, hindsight bias, index card, index fund, Isaac Newton, John Conway, John von Neumann, Large Hadron Collider, Long Term Capital Management, Louis Pasteur, mental accounting, meta-analysis, mirror neurons, money market fund, Monty Hall problem, Nash equilibrium, Necker cube, Nick Bostrom, NP-complete, One Laptop per Child (OLPC), P = NP, paperclip maximiser, pattern recognition, Paul Graham, peak-end rule, Peter Thiel, Pierre-Simon Laplace, placebo effect, planetary scale, prediction markets, random walk, Ray Kurzweil, reversible computing, Richard Feynman, risk tolerance, Rubik’s Cube, Saturday Night Live, Schrödinger's Cat, scientific mainstream, scientific worldview, sensible shoes, Silicon Valley, Silicon Valley startup, Singularitarianism, SpaceShipOne, speech recognition, statistical model, Steve Jurvetson, Steven Pinker, strong AI, sunk-cost fallacy, technological singularity, The Bell Curve by Richard Herrnstein and Charles Murray, the map is not the territory, the scientific method, Turing complete, Turing machine, Tyler Cowen, ultimatum game, X Prize, Y Combinator, zero-sum game

If you limit yourself to simple Boolean propositions of the form ((A or B or C) and (B or ¬C or D) and (D or ¬A or ¬C)…), conjunctions of disjunctions of three variables, then this is a very famous problem called 3-SAT, which is one of the first problems ever to be proven NP-complete. So just because you don’t see a contradiction in the Zombie World at first glance, it doesn’t mean that no contradiction is there. It’s like not seeing a contradiction in the Riemann Hypothesis at first glance. From conceptual possibility (“I don’t see a problem”) to logical possibility, in the full technical sense, is a very great leap. It’s easy to make it an NP-complete leap, and with first-order theories you can make it arbitrarily hard to compute even for finite questions.

…

Chalmers, The Conscious Mind. 222 Zombie Responses I’m a bit tired today, having stayed up until 3 a.m. writing yesterday’s >6,000-word essay on zombies, so today I’ll just reply to Richard, and tie up a loose end I spotted the next day. (A) Richard Chappell writes: A terminological note (to avoid unnecessary confusion): what you call “conceivable,” others of us would merely call “apparently conceivable.” The gap between “I don’t see a contradiction yet” and “this is logically possible” is so huge (it’s NP-complete even in some simple-seeming cases) that you really should have two different words. As the zombie argument is boosted to the extent that this huge gap can be swept under the rug of minor terminological differences, I really think it would be a good idea to say “conceivable” versus “logically possible” or maybe even have a still more visible distinction.

The Art of Computer Programming: Sorting and Searching by Donald Ervin Knuth

card file, Charles Babbage, Claude Shannon: information theory, complexity theory, correlation coefficient, Donald Knuth, double entry bookkeeping, Eratosthenes, Fermat's Last Theorem, G4S, information retrieval, iterative process, John von Neumann, linked data, locality of reference, Menlo Park, Norbert Wiener, NP-complete, p-value, Paul Erdős, RAND corporation, refrigerator car, sorting algorithm, Vilfredo Pareto, Yogi Berra, Zipf's Law

., xn) that are not sorted by such a network, in terms of the behavior of the special subnetwork. b) Given a set of clauses such as (yi V y^ V y-i) A (y2 V y3 V y^) A ..., explain how to construct a special subnetwork such that Fig. 61 sorts all inputs if and only if the clauses are unsatisfiable. [Hence the task of deciding whether a comparator sequence forms a sorting network is co-NP-complete, in the sense of Section 7.9.] 3.3.4 NETWORKS FOR SORTING 243 53. [30] (Periodic sorting networks.) The following two 16-networks illustrate general recursive constructions of t-level networks for n = 2* in the case t = 4: I tx (a) (b) If we number the input lines from 0 to 2* — 1, the Zth level in case (a) has comparators [i:j] where i mod 2t+1~l < 2t~l and j = i © Bt+1~l - 1); there are t2t~~1 comparators altogether, as in the bitonic merge.

…

Non-messing-up theorem, 90, 238, 669. Nondeterministic adversary, 219. Norlund, Niels Erik, 638. Normal deviate, 69. Normal distribution, approximately, 45, 650. Norwegian language, 520. Noshita, Kohei (IFTS ?), 213, 218. Notations, index to, 752-756. Novelli, Jean-Christophe, 614. NOW-Sort, 390. NP-complete problems, 242. Nsort, 390. Null permutation, 25, 36. Number-crunching computers, 175, 381, 389-390. Numerical instability, 41. Nyberg, Christopher, 390. Oberhettinger, Fritz, 131. Oblivious algorithms, 219-220. O'Connor, Daniel J., 225. Octrees, 565. INDEX AND GLOSSARY 771 j Odd-even merge, 223-226, 228, 230, J(l 243, 244.

Superintelligence: Paths, Dangers, Strategies by Nick Bostrom

agricultural Revolution, AI winter, Albert Einstein, algorithmic trading, anthropic principle, Anthropocene, anti-communist, artificial general intelligence, autism spectrum disorder, autonomous vehicles, backpropagation, barriers to entry, Bayesian statistics, bioinformatics, brain emulation, cloud computing, combinatorial explosion, computer vision, Computing Machinery and Intelligence, cosmological constant, dark matter, DARPA: Urban Challenge, data acquisition, delayed gratification, Demis Hassabis, demographic transition, different worldview, Donald Knuth, Douglas Hofstadter, driverless car, Drosophila, Elon Musk, en.wikipedia.org, endogenous growth, epigenetics, fear of failure, Flash crash, Flynn Effect, friendly AI, general purpose technology, Geoffrey Hinton, Gödel, Escher, Bach, hallucination problem, Hans Moravec, income inequality, industrial robot, informal economy, information retrieval, interchangeable parts, iterative process, job automation, John Markoff, John von Neumann, knowledge worker, Large Hadron Collider, longitudinal study, machine translation, megaproject, Menlo Park, meta-analysis, mutually assured destruction, Nash equilibrium, Netflix Prize, new economy, Nick Bostrom, Norbert Wiener, NP-complete, nuclear winter, operational security, optical character recognition, paperclip maximiser, pattern recognition, performance metric, phenotype, prediction markets, price stability, principal–agent problem, race to the bottom, random walk, Ray Kurzweil, recommendation engine, reversible computing, search costs, social graph, speech recognition, Stanislav Petrov, statistical model, stem cell, Stephen Hawking, Strategic Defense Initiative, strong AI, superintelligent machines, supervolcano, synthetic biology, technological singularity, technoutopianism, The Coming Technological Singularity, The Nature of the Firm, Thomas Kuhn: the structure of scientific revolutions, time dilation, Tragedy of the Commons, transaction costs, trolley problem, Turing machine, Vernor Vinge, WarGames: Global Thermonuclear War, Watson beat the top human players on Jeopardy!, World Values Survey, zero-sum game

Poker Varied Computer poker players remain slightly below the best humans for full-ring Texas hold ‘em but perform at a superhuman level in some poker variants.52 FreeCell Superhuman Heuristics evolved using genetic algorithms produce a solver for the solitaire game FreeCell (which in its generalized form is NP-complete) that is able to beat high-ranking human players.53 Go Very strong amateur level As of 2012, the Zen series of go-playing programs has reached rank 6 dan in fast games (the level of a very strong amateur player), using Monte Carlo tree search and machine learning techniques.54 Go-playing programs have been improving at a rate of about 1 dan/year in recent years.

Data Mining: Concepts, Models, Methods, and Algorithms by Mehmed Kantardzić

Albert Einstein, algorithmic bias, backpropagation, bioinformatics, business cycle, business intelligence, business process, butter production in bangladesh, combinatorial explosion, computer vision, conceptual framework, correlation coefficient, correlation does not imply causation, data acquisition, discrete time, El Camino Real, fault tolerance, finite state, Gini coefficient, information retrieval, Internet Archive, inventory management, iterative process, knowledge worker, linked data, loose coupling, Menlo Park, natural language processing, Netflix Prize, NP-complete, PageRank, pattern recognition, peer-to-peer, phenotype, random walk, RFID, semantic web, speech recognition, statistical model, Telecommunications Act of 1996, telemarketer, text mining, traveling salesman, web application

Ideally, we would like to choose a test at each stage of sample-set splitting so that the final tree is small. Since we are looking for a compact decision tree that is consistent with the training set, why not explore all possible trees and select the simplest? Unfortunately, the problem of finding the smallest decision tree consistent with a training data set is NP-complete. Enumeration and analysis of all possible trees will cause a combinatorial explosion for any real-world problem. For example, for a small database with five attributes and only 20 training examples, the possible number of decision trees is greater than 106, depending on the number of different values for every attribute.

Masterminds of Programming: Conversations With the Creators of Major Programming Languages by Federico Biancuzzi, Shane Warden

Benevolent Dictator For Life (BDFL), business intelligence, business logic, business process, cellular automata, cloud computing, cognitive load, commoditize, complexity theory, conceptual framework, continuous integration, data acquisition, Dennis Ritchie, domain-specific language, Douglas Hofstadter, Fellow of the Royal Society, finite state, Firefox, follow your passion, Frank Gehry, functional programming, general-purpose programming language, Guido van Rossum, higher-order functions, history of Unix, HyperCard, industrial research laboratory, information retrieval, information security, iterative process, Ivan Sutherland, John von Neumann, Ken Thompson, Larry Ellison, Larry Wall, linear programming, loose coupling, machine readable, machine translation, Mars Rover, millennium bug, Multics, NP-complete, Paul Graham, performance metric, Perl 6, QWERTY keyboard, RAND corporation, randomized controlled trial, Renaissance Technologies, Ruby on Rails, Sapir-Whorf hypothesis, seminal paper, Silicon Valley, slashdot, software as a service, software patent, sorting algorithm, SQL injection, Steve Jobs, traveling salesman, Turing complete, type inference, Valgrind, Von Neumann architecture, web application

Computer Science What constitutes research in computer science? Al: This is a wonderful question, and one that does not have a well-defined answer. I think computer science research has broadened enormously in its scope. We still have the deep, unsolved, quintessential questions of computer science: how do we prove that a problem like factoring or an NP-complete problem is actually hard; how do we model complex systems like a human cell or the human brain; how can we construct scalable, trustworthy systems; how can programmers build arbitrarily reliable software; how can we make software with human-friendly characteristics like emotion or intelligence; how far can we extend Moore’s Law?