P = NP

31 results back to index


pages: 236 words: 50,763

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

Interested parties must apply directly to Random House, Inc. for permission. All Rights Reserved Library of Congress Cataloging-in-Publication Data Fortnow, Lance, 1963– The golden ticket : P, NP, and the search for the impossible / Lance Fortnow. pages cm Summary: “The P-NP problem is the most important open problem in computer science, if not all of mathematics. The Golden Ticket provides a nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond. In this informative and entertaining book, Lance Fortnow traces how the problem arose during the Cold War on both sides of the Iron Curtain, and gives examples of the problem from a variety of disciplines, including economics, physics, and biology.

The most prestigious computer science journal receives a steady stream of papers claiming to resolve the P versus NP question and has a specific policy for those papers: The Journal of the ACM frequently receives submissions purporting to solve a long-standing open problem in complexity theory, such as the P/NP problem. Such submissions tax the voluntary editorial and peer-reviewing resources used by JACM, by requiring the review process to identify the errors in them. JACM remains open to the possibility of eventual resolution of P/NP and related questions, and continues to welcome submissions on the subject. However, to mitigate the burden of repeated resubmissions of incremental corrections of errors identified during editorial review, JACM has adopted the following policy: No author may submit more than one paper on the P/NP or related long-standing questions in complexity theory in any 24 month period, except by invitation of the Editor-in-Chief.

In this informative and entertaining book, Lance Fortnow traces how the problem arose during the Cold War on both sides of the Iron Curtain, and gives examples of the problem from a variety of disciplines, including economics, physics, and biology. He explores problems that capture the full difficulty of the P-NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook. But difficulty also has its advantages. Hard problems allow us to safely conduct electronic commerce and maintain privacy in our online lives. The Golden Ticket explores what we truly can and cannot achieve computationally, describing the benefits and unexpected challenges of the P-NP problem”—Provided by publisher. Includes bibliographical references and index. ISBN 978-0-691-15649-1 (hardback) 1.


pages: 262 words: 65,959

pages: 523 words: 143,139

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

The intractable scheduling problems that Eugene Lawler encountered in chapter 5 fall into this category. An NP-hard problem that is itself in NP is known as “NP-complete.” See Karp, “Reducibility Among Combinatorial Problems,” for the classic result showing that a version of the traveling salesman problem is NP-complete, and Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, for an accessible introduction to P and NP. most computer scientists believe 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.

______. “The Traveling-Salesman Problem.” Operations Research 4, no. 1 (1956): 61–75. ______. “What Future Is There for Intelligent Machines?” Audio Visual Communication Review 11, no. 6 (1963): 260–270. Forster, Edward M. Howards End. London: Edward Arnold, 1910. Fortnow, Lance. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton, NJ: Princeton University Press, 2013. Fraker, Guy C. “The Real Lincoln Highway: The Forgotten Lincoln Circuit Markers.” Journal of the Abraham Lincoln Association 25 (2004): 76–97. Frank, Robert H. “If Homo Economicus Could Choose His Own Utility Function, Would He Want One with a Conscience?”


pages: 284 words: 79,265

pages: 346 words: 97,890

pages: 504 words: 89,238

Natural language processing with Python by Steven Bird, Ewan Klein, Edward Loper

bioinformatics, business intelligence, business logic, Computing Machinery and Intelligence, conceptual framework, Donald Knuth, duck typing, elephant in my pajamas, en.wikipedia.org, finite state, Firefox, functional programming, Guido van Rossum, higher-order functions, information retrieval, language acquisition, lolcat, machine translation, Menlo Park, natural language processing, P = NP, search inside the book, sparse data, speech recognition, statistical model, text mining, Turing test, W. E. B. Du Bois

To begin with, we construct a list of bigrams whose members are themselves word-tag pairs, such as (('The', 'DET'), ('Fulton', 'NP')) and (('Fulton', 'NP'), ('County', 'N')). Then we construct a FreqDist from the tag parts of the bigrams. >>> word_tag_pairs = nltk.bigrams(brown_news_tagged) >>> list(nltk.FreqDist(a[1] for (a, b) in word_tag_pairs if b[1] == 'N')) ['DET', 'ADJ', 'N', 'P', 'NP', 'NUM', 'V', 'PRO', 'CNJ', '.', ',', 'VG', 'VN', ...] This confirms our assertion that nouns occur after determiners and adjectives, including numeral adjectives (tagged as NUM). Verbs Verbs are words that describe events and actions, e.g., fall and eat, as shown in Table 5-3. In the context of a sentence, verbs typically express a relation involving the referents of one or more noun phrases.

Ubiquitous Ambiguity A well-known example of ambiguity is shown in (2), from the Groucho Marx movie, Animal Crackers (1930): (2) While hunting in Africa, I shot an elephant in my pajamas. How an elephant got into my pajamas I’ll never know. Let’s take a closer look at the ambiguity in the phrase: I shot an elephant in my pajamas. First we need to define a simple grammar: >>> ... ... ... ... ... ... ... ... ... groucho_grammar = nltk.parse_cfg(""" S -> NP VP PP -> P NP NP -> Det N | Det N PP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' N -> 'elephant' | 'pajamas' V -> 'shot' P -> 'in' """) 8.1 Some Grammatical Dilemmas | 293 This grammar permits the sentence to be analyzed in two ways, depending on whether the prepositional phrase in my pajamas describes the elephant or the shooting event. >>> sent = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas'] >>> parser = nltk.ChartParser(groucho_grammar) >>> trees = parser.nbest_parse(sent) >>> for tree in trees: ... print tree (S (NP I) (VP (V shot) (NP (Det an) (N elephant) (PP (P in) (NP (Det my) (N pajamas)))))) (S (NP I) (VP (VP (V shot) (NP (Det an) (N elephant))) (PP (P in) (NP (Det my) (N pajamas))))) The program produces two bracketed structures, which we can depict as trees, as shown in (3): (3) a.

By convention, the lefthand side of the first production is the start-symbol of the grammar, typically S, and all well-formed trees must have this symbol as their root label. In NLTK, contextfree grammars are defined in the nltk.grammar module. In Example 8-1 we define a grammar and show how to parse a simple sentence admitted by the grammar. Example 8-1. A simple context-free grammar. grammar1 = nltk.parse_cfg(""" S -> NP VP VP -> V NP | V NP PP PP -> P NP V -> "saw" | "ate" | "walked" NP -> "John" | "Mary" | "Bob" | Det N | Det N PP Det -> "a" | "an" | "the" | "my" N -> "man" | "dog" | "cat" | "telescope" | "park" P -> "in" | "on" | "by" | "with" """) >>> sent = "Mary saw Bob".split() >>> rd_parser = nltk.RecursiveDescentParser(grammar1) >>> for tree in rd_parser.nbest_parse(sent): ... print tree (S (NP Mary) (VP (V saw) (NP Bob))) The grammar in Example 8-1 contains productions involving various syntactic categories, as laid out in Table 8-1.



pages: 369 words: 80,355

Too Big to Know: Rethinking Knowledge Now That the Facts Aren't the Facts, Experts Are Everywhere, and the Smartest Person in the Room Is the Room by David Weinberger

airport security, Alfred Russel Wallace, Alvin Toffler, Amazon Mechanical Turk, An Inconvenient Truth, Berlin Wall, Black Swan, book scanning, Cass Sunstein, commoditize, Computer Lib, corporate social responsibility, crowdsourcing, Danny Hillis, David Brooks, Debian, double entry bookkeeping, double helix, Dr. Strangelove, en.wikipedia.org, Exxon Valdez, Fall of the Berlin Wall, future of journalism, Future Shock, Galaxy Zoo, Gregor Mendel, Hacker Ethic, Haight Ashbury, Herman Kahn, hive mind, Howard Rheingold, invention of the telegraph, Jeff Hawkins, jimmy wales, Johannes Kepler, John Harrison: Longitude, Kevin Kelly, Large Hadron Collider, linked data, Neil Armstrong, Netflix Prize, New Journalism, Nicholas Carr, Norbert Wiener, off-the-grid, openstreetmap, P = NP, P vs NP, PalmPilot, Pluto: dwarf planet, profit motive, Ralph Waldo Emerson, RAND corporation, Ray Kurzweil, Republic of Letters, RFID, Richard Feynman, Ronald Reagan, scientific management, semantic web, slashdot, social graph, Steven Pinker, Stewart Brand, systems thinking, technological singularity, Ted Nelson, the Cathedral and the Bazaar, the scientific method, The Wisdom of Crowds, Thomas Kuhn: the structure of scientific revolutions, Thomas Malthus, Whole Earth Catalog, X Prize

Indeed, the space within which credentialed science occurs is becoming dramatically and usefully more entwined with the rest of its environment. For example, on August 6, 2010, the mathematician Vinay Deolalikar sent to his colleagues a manuscript proposing a solution to a mathematical problem so notoriously difficult that there’s a million-dollar prize for solving it.34 The “P≠NP” problem had previously brought down some seriously brilliant mathematicians who thought they had it licked. This time, however, the person who originally formulated the problem emailed Deolalikar’s solution to some of his colleagues, saying, “This appears to be a relatively serious claim to have solved P vs.


Elliptic Tales: Curves, Counting, and Number Theory by Avner Ash, Robert Gross

Andrew Wiles, fudge factor, Georg Cantor, P = NP

The set E(Fp )ns is still nonempty, and is in fact also an abelian group, just as E(Fp ) was for good p, as we saw in chapter 9. We let Np stand for the number of points in E(Fp )ns . For the good primes p, E modulo p is nonsingular, so Np is simply the number of points in E(Fp ). For the bad primes p, we worked out Np in chapter 9. The results, taken from table 9.4, are that Np = p if E has additive reduction at p, Np = p − 1 if E has split multiplicative reduction at p, and Np = p + 1 if E has nonsplit multiplicative reduction at p. Next we review the definition of the integer ap , defined for every prime p . If E modulo p is nonsingular (good p), we set Np = p + 1 − ap . 208 CHAPTER 13 If E modulo p is singular (bad p), we set Np = p − ap , where we took away 1 because E(Fp ) has one singular point that we are not counting.


pages: 211 words: 57,618

pages: 396 words: 117,149

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


pages: 291 words: 81,703

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

Brassard, “Quantum Public Key Distribution Reinvented,” SIGACT News, v. 18, n. 4, 1987, pp. 51–53. 127. C.H. Bennett and G. Brassard, “The Dawn of a New Era for Quantum Cryptography: The Experimental Prototype is Working!” SIGACT News, v. 20, n. 4, Fall 1989, pp. 78–82. 128. C.H. Bennett, G. Brassard, and S. Breidbart, Quantum Cryptography II: How to Re–Use a One–Time Pad Safely Even if P=NP, unpublished manuscript, Nov 1982. 129. C.H. Bennett, G. Brassard, S. Breidbart, and S. Weisner, “Quantum Cryptography, or Unforgeable Subway Tokens,” Advances in Cryptology: Proceedings of Crypto 82, Plenum Press, 1983, pp. 267–275. 130. C.H. Bennett, G. Brassard, C. Crépeau, and M.–H. Skubiszewska, “Practical Quantum Oblivious Transfer,” Advances in Cryptology—CRYPTO ’91 Proceedings, Springer–Verlag, 1992, pp. 351–366. 131.


pages: 406 words: 108,266

pages: 275 words: 77,017


pages: 434 words: 135,226

The Haskell Road to Logic, Maths and Programming by Kees Doets, Jan van Eijck, Jan Eijck

Albert Einstein, Charles Babbage, Eratosthenes, functional programming, Georg Cantor, P = NP, Russell's paradox


Syntactic Structures by Noam Chomsky

finite state, language acquisition, P = NP, statistical model


pages: 416 words: 39,022

How I Became a Quant: Insights From 25 of Wall Street's Elite by Richard R. Lindsey, Barry Schachter

Albert Einstein, algorithmic trading, Andrew Wiles, Antoine Gombaud: Chevalier de Méré, asset allocation, asset-backed security, backtesting, bank run, banking crisis, Bear Stearns, Black-Scholes formula, Bob Litterman, Bonfire of the Vanities, book value, Bretton Woods, Brownian motion, business cycle, business process, butter production in bangladesh, buy and hold, buy low sell high, capital asset pricing model, centre right, collateralized debt obligation, commoditize, computerized markets, corporate governance, correlation coefficient, creative destruction, Credit Default Swap, credit default swaps / collateralized debt obligations, currency manipulation / currency intervention, currency risk, discounted cash flows, disintermediation, diversification, Donald Knuth, Edward Thorp, Emanuel Derman, en.wikipedia.org, Eugene Fama: efficient market hypothesis, financial engineering, financial innovation, fixed income, full employment, George Akerlof, global macro, Gordon Gekko, hiring and firing, implied volatility, index fund, interest rate derivative, interest rate swap, Ivan Sutherland, John Bogle, John von Neumann, junk bonds, linear programming, Loma Prieta earthquake, Long Term Capital Management, machine readable, margin call, market friction, market microstructure, martingale, merger arbitrage, Michael Milken, Myron Scholes, Nick Leeson, P = NP, pattern recognition, Paul Samuelson, pensions crisis, performance metric, prediction markets, profit maximization, proprietary trading, purchasing power parity, quantitative trading / quantitative finance, QWERTY keyboard, RAND corporation, random walk, Ray Kurzweil, Reminiscences of a Stock Operator, Richard Feynman, Richard Stallman, risk free rate, risk-adjusted returns, risk/return, seminal paper, shareholder value, Sharpe ratio, short selling, Silicon Valley, six sigma, sorting algorithm, statistical arbitrage, statistical model, stem cell, Steven Levy, stochastic process, subscription business, systematic trading, technology bubble, The Great Moderation, the scientific method, too big to fail, trade route, transaction costs, transfer pricing, value at risk, volatility smile, Wiener process, yield curve, young professional


pages: 1,331 words: 163,200

pages: 673 words: 164,804

pages: 245 words: 12,162

pages: 641 words: 182,927

pages: 408 words: 85,118

Python for Finance by Yuxing Yan

asset-backed security, book value, business cycle, business intelligence, capital asset pricing model, constrained optimization, correlation coefficient, data science, distributed generation, diversified portfolio, financial engineering, functional programming, implied volatility, market microstructure, P = NP, p-value, quantitative trading / quantitative finance, risk free rate, Sharpe ratio, tail risk, time value of money, value at risk, volatility smile, zero-sum game

In the following program, we have three input values: ticker, begdate (first date), and enddate (second date): import datetime import matplotlib.pyplot as plt from matplotlib.finance import quotes_historical_yahoo from matplotlib.dates import MonthLocator,DateFormatter ticker='AAPL' begdate= datetime.date( 2012, 1, 2 ) enddate = datetime.date( 2013, 12,4) months = MonthLocator(range(1,13), bymonthday=1, interval=3) # every 3rd month monthsFmt = DateFormatter("%b '%Y") x = quotes_historical_yahoo(ticker, begdate, enddate) if len(x) == 0: print ('Found no quotes') raise SystemExit dates = [q[0] for q in x] closes = [q[4] for q in x] fig, ax = plt.subplots() ax.plot_date(dates, closes, '-') ax.xaxis.set_major_locator(months) ax.xaxis.set_major_formatter(monthsFmt) ax.xaxis.set_minor_locator(mondays) ax.autoscale_view() ax.grid(True) fig.autofmt_xdate() [ 153 ] Visual Finance via Matplotlib The output graph is shown as follows: IBM's intra-day graphical representations We could demonstrate the price movement of a stock for a given period, for example, from January 2009 to today. First, let's look at the intra-day price pattern. The following program will be explained in the next chapter: import pandas as pd, numpy as np, datetime ticker='AAPL' path='http://www.google.com/finance/getprices?q=ttt&i=60&p=1d&f=d,o,h,l,c ,v' p=np.array(pd.read_csv(path.replace('ttt',ticker),skiprows=7,header=No ne)) date=[] for i in arange(0,len(p)): if p[i][0][0]=='a': t= datetime.datetime.fromtimestamp(int(p[i][0].replace('a',''))) date.append(t) else: date.append(t+datetime.timedelta(minutes =int(p[i][0]))) [ 154 ] Chapter 7 final=pd.DataFrame(p,index=date) final.columns=['a','Open','High','Low','Close','Vol'] del final['a'] x=final.index y=final.Close title('Intraday price pattern for ttt'.replace('ttt',ticker)) xlabel('Price of stock') ylabel('Intro-day price pattern') plot(x,y) show() The graph is shown in the following image: [ 155 ] Visual Finance via Matplotlib A more complex program that we can run to find the intra-day pattern could be found at http://matplotlib.org/examples/pylab_examples/finance_work2. html.

In addition, sometimes we have to convert daily returns to weekly or monthly, or convert monthly returns to quarterly or annual. Thus, understanding how to estimate returns and their conversion is vital. Assume that we have four prices and we choose the first and last three prices as follows: >>>import numpy as np >>>p=np.array([1,1.1,0.9,1.05]) [ 185 ] Statistical Analysis of Time Series It is important how these prices are sorted. If the first price happened before the second price, we know that the first return should be (1.1-1)/1=10%. Next, we learn how to retrieve the first n-1 and the last n-1 records from an n-record array.

This correlation is represented in the following code: import numpy as np import statsmodels.api as sm from matplotlib.finance import quotes_historical_yahoo begdate=(2013,10,1) enddate=(2013,10,30) ticker='IBM' #WMT data= quotes_historical_yahoo(ticker, begdate, enddate,asobject=True, adjusted=True) p=np.array(data.aclose) dollar_vol=np.array(data.volume*p) ret=np.array((p[1:] - p[:-1])/p[1:]) illiq=mean(np.divide(abs(ret),dollar_vol[1:])) print("Aminud illiq=", illiq) ('Aminud illiq=', 1.1650681670001537e-11) Pastor and Stambaugh (2003) liquidity measure Based on the methodology and empirical evidence in Campbell, Grossman, and Wang (1993), Pastor and Stambaugh (2003) designed the following model to measure individual stock's liquidity and the market liquidity: \W D E [W E [W W (9) Here, yt is the excess stock return, 5W 5 I W , on day t, 5W is the return for the stock, 5 I W is the risk-free rate, [W is the market return; [W is the signed dollar trading volume ( x2,t = sign Rt − R f ,t ∗ pt ∗ volumet), pt is the stock price, and YROXPHW is the trading volume.


pages: 571 words: 105,054

pages: 400 words: 94,847

pages: 416 words: 112,268

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


pages: 482 words: 122,497

The Wrecking Crew: How Conservatives Rule by Thomas Frank

"Hurricane Katrina" Superdome, affirmative action, Alan Greenspan, anti-communist, barriers to entry, Berlin Wall, Bernie Madoff, British Empire, business cycle, classic study, collective bargaining, corporate governance, Credit Default Swap, David Brooks, disinformation, edge city, financial deregulation, full employment, George Gilder, guest worker program, Ida Tarbell, income inequality, invisible hand, job satisfaction, Michael Milken, Mikhail Gorbachev, Mont Pelerin Society, mortgage debt, Naomi Klein, Nelson Mandela, new economy, P = NP, plutocrats, Ponzi scheme, Ralph Nader, rent control, Richard Florida, road to serfdom, rolodex, Ronald Reagan, school vouchers, shareholder value, Silicon Valley, stem cell, stock buybacks, Strategic Defense Initiative, Telecommunications Act of 1996, the scientific method, too big to fail, Triangle Shirtwaist Factory, union organizing, War on Poverty

.: Conservative Caucus, 1983), p. 181. 27. The word “revolution” could even take on the wistful notes of lost youth, as at a 1992 College Republican reunion when Abramoff, by then a producer of wretched movies, hosted an alumni session called “Rejoin the Revolution.” See 1992 College Republicans’ Centennial Celebration (n.p.: n.p., n.d. [1992]). Sword and shield: “Message from the Chairman” in the 1983 Annual Report of the College Republicans, p. 3. The phrase is also used in the 1982 Review of the NEWS interview cited above and in a 1995 profile by John W. Moore, “A Lobbyist With a Line to Capitol Hill,” National Journal, July 29, 1995.

Since the breaking of the Abramoff scandal, however, Waller has become a frequent critic of the fallen lobbyist, recounting for other journalists how Abramoff played Washington’s right-wing network for his various lobbying clients. (He did not respond to inquiries from me.) “Deputy projects director”: College Republican National Committee, Forty-Fifth Biennial Convention (n.p.: n.p., 1983), n.p. YAF magazine: J. Michael Waller, “Bare-Fisted Journalism,” New Guard, Winter 1982–83, p. 37. Crashing the IPS party: CR Report, May 14, 1983, p. 2. USA Foundation: J. Michael Waller, “CISPES: A Guerrilla Propaganda Network,” a twenty-one-page report printed on United Students of America Foundation letterhead, with a cover letter signed by Jack Abramoff and dated November 7, 1983, from collections of Political Research Associates.

“CNMI policy permits the staffing of major employers in the territory—garment factories, security companies, the hotel industry—with a permanent floating army of foreign workers who have no opportunity to become permanent members of the community and who, by nature of their status, culture and powerlessness, are extremely vulnerable to exploitation, pressure, and mistreatment.” Congressman George Miller and Democratic Staff of the House Committee on Resources, “Beneath the American Flag: Labor and Human Rights Abuses in the CNMI” (n.p.: n.p., March 26, 1998), p. 15. 9. “The fact that an employer can have an alien worker removed from the CNMI on one-day’s notice is a powerful incentive for an alien to obey an employer’s demands, even though the demands may be illegal or abusive.” Third Annual Report, p. 11. 10. As of 1997, the minimum wage in Saipan for garment and construction workers was $2.90 per hour; for more exalted occupations it was $3.05 per hour.


pages: 476 words: 121,460

The Man From the Future: The Visionary Life of John Von Neumann by Ananyo Bhattacharya

Ada Lovelace, AI winter, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Alvin Roth, Andrew Wiles, Benoit Mandelbrot, business cycle, cellular automata, Charles Babbage, Claude Shannon: information theory, clockwork universe, cloud computing, Conway's Game of Life, cuban missile crisis, Daniel Kahneman / Amos Tversky, DeepMind, deferred acceptance, double helix, Douglas Hofstadter, Dr. Strangelove, From Mathematics to the Technologies of Life and Death, Georg Cantor, Greta Thunberg, Gödel, Escher, Bach, haute cuisine, Herman Kahn, indoor plumbing, Intergovernmental Panel on Climate Change (IPCC), Isaac Newton, Jacquard loom, Jean Tirole, John Conway, John Nash: game theory, John von Neumann, Kenneth Arrow, Kickstarter, linear programming, mandelbrot fractal, meta-analysis, mutually assured destruction, Nash equilibrium, Norbert Wiener, Norman Macrae, P = NP, Paul Samuelson, quantum entanglement, RAND corporation, Ray Kurzweil, Richard Feynman, Ronald Reagan, Schrödinger's Cat, second-price auction, side project, Silicon Valley, spectrum auction, Steven Levy, Strategic Defense Initiative, technological singularity, Turing machine, Von Neumann architecture, zero-sum game

Macrae, John von Neumann. 102. ‘Benoît Mandelbrot – Post-doctoral Studies: Weiner and Von Neumann (36/144)’, Web of Stories – Life Stories of Remarkable People, https://www.youtube.com/watch?v=U9kw6Reml6s. 103. https://rjlipton.wpcomstaging.com/the-gdel-letter/. Also see Richard J. Lipton, 2010, The P=NP Question and Gödel’s Lost Letter, Springer, New York. 104. John von Neumann to Marina von Neumann, 19 April 1955, quoted in von Neumann Whitman, The Martian’s Daughter. 105. Quoted in Dyson, Turing’s Cathedral. 106. Quoted in ibid. 107. Email to author. 108. John von Neumann, Documentary Mathematical Association of America, 1966. 109.


pages: 525 words: 149,886


pages: 968 words: 224,513

Global Catastrophic Risks by Nick Bostrom, Milan M. Cirkovic

affirmative action, agricultural Revolution, Albert Einstein, American Society of Civil Engineers: Report Card, anthropic principle, artificial general intelligence, Asilomar, availability heuristic, backpropagation, behavioural economics, Bill Joy: nanobots, Black Swan, carbon tax, carbon-based life, Charles Babbage, classic study, cognitive bias, complexity theory, computer age, coronavirus, corporate governance, cosmic microwave background, cosmological constant, cosmological principle, cuban missile crisis, dark matter, death of newspapers, demographic transition, Deng Xiaoping, distributed generation, Doomsday Clock, Drosophila, endogenous growth, Ernest Rutherford, failed state, false flag, feminist movement, framing effect, friendly AI, Georg Cantor, global pandemic, global village, Great Leap Forward, Gödel, Escher, Bach, Hans Moravec, heat death of the universe, hindsight bias, information security, Intergovernmental Panel on Climate Change (IPCC), invention of agriculture, Kevin Kelly, Kuiper Belt, Large Hadron Collider, launch on warning, Law of Accelerating Returns, life extension, means of production, meta-analysis, Mikhail Gorbachev, millennium bug, mutually assured destruction, Nick Bostrom, nuclear winter, ocean acidification, off-the-grid, Oklahoma City bombing, P = NP, peak oil, phenotype, planetary scale, Ponzi scheme, power law, precautionary principle, prediction markets, RAND corporation, Ray Kurzweil, Recombinant DNA, reversible computing, Richard Feynman, Ronald Reagan, scientific worldview, Singularitarianism, social intelligence, South China Sea, strong AI, superintelligent machines, supervolcano, synthetic biology, technological singularity, technoutopianism, The Coming Technological Singularity, the long tail, The Turner Diaries, Tunguska event, twin studies, Tyler Cowen, uranium enrichment, Vernor Vinge, War on Poverty, Westphalian system, Y2K


pages: 1,737 words: 491,616

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