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, Johannes Kepler, John von Neumann, linear programming, new economy, NP-complete, Occam's razor, P = NP, Paul Erdős, Richard Feynman, Rubik’s Cube, smart grid, Stephen Hawking, traveling salesman, Turing machine, Turing test, Watson beat the top human players on Jeopardy!, William of Occam

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

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. This applies to resubmissions of previously rejected manuscripts.

THE GOLDEN TICKET THE GOLDEN TICKET P, NP, AND THE SEARCH FOR THE IMPOSSIBLE LANCE FORTNOW PRINCETON UNIVERSITY PRESS PRINCETON AND OXFORD Copyright © 2013 by Princeton University Press Published by Princeton University Press, 41 William Street, Princeton, New Jersey 08540 In the United Kingdom: Princeton University Press, 6 Oxford Street, Woodstock, Oxfordshire OX20 1TW press.princeton.edu The epigraph for this book is taken from Charlie and the Chocolate Factory by Roald Dahl, copyright © 1964, renewed 1992 by Roald Dahl Nominee Limited. Used by permission of Alfred A. Knopf, an imprint of Random House Children’s Books, a division of Random House, Inc. Any third party use of this material, outside of this publication, is prohibited. Interested parties must apply directly to Random House, Inc. for permission.


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 trading, anthropic principle, asset allocation, autonomous vehicles, Bayesian statistics, Berlin Wall, Bill Duvall, bitcoin, Community Supported Agriculture, complexity theory, constrained optimization, cosmological principle, cryptocurrency, Danny Hillis, David Heinemeier Hansson, delayed gratification, dematerialisation, diversification, Donald Knuth, double helix, Elon Musk, fault tolerance, Fellow of the Royal Society, Firefox, first-price auction, Flash crash, Frederick Winslow Taylor, George Akerlof, global supply chain, Google Chrome, Henri Poincaré, information retrieval, Internet Archive, Jeff Bezos, Johannes Kepler, John Nash: game theory, John von Neumann, Kickstarter, knapsack problem, Lao Tzu, Leonard Kleinrock, linear programming, martingale, Nash equilibrium, natural language processing, NP-complete, P = NP, packet switching, Pierre-Simon Laplace, prediction markets, race to the bottom, RAND corporation, RFC: Request For Comment, Robert X Cringely, Sam Altman, 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, traveling salesman, Turing machine, urban planning, Vickrey auction, Vilfredo Pareto, Walter Mischel, Y Combinator, zero-sum game

(In “A Terminological Proposal,” Donald Knuth suggested this as an appropriate label for NP-hard problems, in addition to offering a live turkey to anybody who could prove P = NP.) 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.

______. “Some Experimental Games.” In Research Memorandum RM-789. Santa Monica, CA: RAND, 1952. ______. “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?” American Economic Review 1987, 593–604. ______. Passions within Reason: The Strategic Role of the Emotions.


pages: 284 words: 79,265

pages: 504 words: 89,238

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

bioinformatics, business intelligence, conceptual framework, Donald Knuth, elephant in my pajamas, en.wikipedia.org, finite state, Firefox, Guido van Rossum, information retrieval, Menlo Park, natural language processing, P = NP, search inside the book, speech recognition, statistical model, text mining, Turing test

Mary’s intelligence impressed her teachers The simplified noun tags are N for common nouns like book, and NP for proper nouns like Scotland. 184 | Chapter 5: Categorizing and Tagging Words Let’s inspect some tagged text to see what parts-of-speech occur before a noun, with the most frequent ones first. 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, Amazon Mechanical Turk, Berlin Wall, Black Swan, book scanning, Cass Sunstein, commoditize, corporate social responsibility, crowdsourcing, Danny Hillis, David Brooks, Debian, double entry bookkeeping, double helix, en.wikipedia.org, Exxon Valdez, Fall of the Berlin Wall, future of journalism, Galaxy Zoo, Hacker Ethic, Haight Ashbury, hive mind, Howard Rheingold, invention of the telegraph, jimmy wales, Johannes Kepler, John Harrison: Longitude, Kevin Kelly, linked data, Netflix Prize, New Journalism, Nicholas Carr, Norbert Wiener, openstreetmap, P = NP, Pluto: dwarf planet, profit motive, Ralph Waldo Emerson, RAND corporation, Ray Kurzweil, Republic of Letters, RFID, Richard Feynman, Ronald Reagan, semantic web, slashdot, social graph, Steven Pinker, Stewart Brand, technological singularity, Ted Nelson, the scientific method, The Wisdom of Crowds, Thomas Kuhn: the structure of scientific revolutions, Thomas Malthus, Whole Earth Catalog, X Prize

We’re just beginning to understand how.”33 That insight, and its development, occurred within a network of amateurs; had it been only a single person’s observation, the importance of “green peas” would not have been noticed. 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. NP.” This highly authoritative endorsement made the paper go viral, at least within the limited world of mathematicians interested in such matters.


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: 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, basic income, Bayesian statistics, Benoit Mandelbrot, bioinformatics, Black Swan, Brownian motion, cellular automata, Claude Shannon: information theory, combinatorial explosion, computer vision, constrained optimization, correlation does not imply causation, creative destruction, crowdsourcing, Danny Hillis, data is the new oil, double helix, Douglas Hofstadter, Erik Brynjolfsson, experimental subject, Filter Bubble, future of work, global village, Google Glasses, Gödel, Escher, Bach, information retrieval, job automation, John Markoff, John Snow's cholera map, John von Neumann, Joseph Schumpeter, Kevin Kelly, lone genius, mandelbrot fractal, Mark Zuckerberg, Moneyball by Michael Lewis explains big data, Narrative Science, Nate Silver, natural language processing, Netflix Prize, Network effects, NP-complete, off grid, P = NP, PageRank, pattern recognition, phenotype, planetary scale, 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 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, 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, Exxon Valdez, fault tolerance, finite state, invisible hand, John von Neumann, knapsack problem, MITM: man-in-the-middle, NP-complete, P = NP, packet switching, RAND corporation, RFC: Request For Comment, software patent, telemarketer, traveling salesman, Turing machine, web of trust, Zimmermann PGP

Bennett and G. 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: 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, Eratosthenes, Georg Cantor, P = NP, Russell's paradox


Syntactic Structures by Noam Chomsky

finite state, 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, Black-Scholes formula, Bonfire of the Vanities, 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, discounted cash flows, disintermediation, diversification, Donald Knuth, Edward Thorp, Emanuel Derman, en.wikipedia.org, Eugene Fama: efficient market hypothesis, financial innovation, fixed income, full employment, George Akerlof, Gordon Gekko, hiring and firing, implied volatility, index fund, interest rate derivative, interest rate swap, John von Neumann, linear programming, Loma Prieta earthquake, Long Term Capital Management, margin call, market friction, market microstructure, martingale, merger arbitrage, Myron Scholes, Nick Leeson, P = NP, pattern recognition, Paul Samuelson, pensions crisis, performance metric, prediction markets, profit maximization, purchasing power parity, quantitative trading / quantitative finance, QWERTY keyboard, RAND corporation, random walk, Ray Kurzweil, Richard Feynman, Richard Stallman, risk-adjusted returns, risk/return, shareholder value, Sharpe ratio, short selling, Silicon Valley, six sigma, sorting algorithm, statistical arbitrage, statistical model, stem cell, Steven Levy, stochastic process, 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: 245 words: 12,162

pages: 641 words: 182,927

pages: 408 words: 85,118

Python for Finance by Yuxing Yan

asset-backed security, business cycle, business intelligence, capital asset pricing model, constrained optimization, correlation coefficient, distributed generation, diversified portfolio, implied volatility, market microstructure, P = NP, p-value, quantitative trading / quantitative finance, Sharpe ratio, 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.

Only affects DataFrame / 2d ndarray input Return estimation If we have price data, we have to calculate returns. 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. To list the first n-1 prices, we use p[:-1], while for the last three prices we use p[1:] as shown in the following code: >>>print(p[:-1]) >>>print(p[1:]) [ 1. 1.1 [ 1.1 0.9 0.9] 1.05] To estimate returns, use the following code: >>>ret=(p[1:]-p[:-1])/p[:-1] >>>print ret [ 0.1 -0.18181818 0.16666667] However, if the prices are arranged in the reverse order, for example, the first one is the latest price and the last one is the oldest price, then we have to estimate returns in the following ways: >>>ret=(p[:-1]-p[1:])/p[1:] >>>print ret [-0.09090909 0.22222222 -0.14285714] >>> The following code shows how to download daily price data from Yahoo!

If we estimate the illiquidity for DELL over the same period, we would find a value of 0.638*10-11. Since 1.165 is greater than 0.638, we conclude that IBM is less liquid than DELL. 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: 400 words: 94,847

pages: 571 words: 105,054

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, Andrew Wiles, artificial general intelligence, Asilomar, Asilomar Conference on Recombinant DNA, augmented reality, autonomous vehicles, basic income, blockchain, brain emulation, Cass Sunstein, Claude Shannon: information theory, complexity theory, computer vision, connected car, crowdsourcing, Daniel Kahneman / Amos Tversky, delayed gratification, Elon Musk, en.wikipedia.org, Erik Brynjolfsson, Ernest Rutherford, Flash crash, full employment, future of work, Gerolamo Cardano, 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, Mark Zuckerberg, Nash equilibrium, Norbert Wiener, NP-complete, openstreetmap, P = NP, Pareto efficiency, Paul Samuelson, Pierre-Simon Laplace, positional goods, probability theory / Blaise Pascal / Pierre de Fermat, profit maximization, RAND corporation, random walk, Ray Kurzweil, recommendation engine, RFID, Richard Thaler, ride hailing / ride sharing, Robert Shiller, Robert Shiller, 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, Thales of Miletus, The Future of Employment, Thomas Bayes, Thorstein Veblen, transport as a service, Turing machine, Turing test, universal basic income, uranium enrichment, Von Neumann architecture, Wall-E, 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

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

Phillips reprinted the memo as appendix B in his book The New Right at Harvard (Vienna, Va.: 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. “Fighting for the Revolution”: CR Report, May 14, 1983, p. 5. 1984 Republican Convention: Raleigh E.

Waller also thanks Abramoff in the acknowledgments of his 1991 book, The Third Current of Revolution. 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: 525 words: 149,886

Higher-Order Perl: A Guide to Program Transformation by Mark Jason Dominus

always be closing, Defenestration of Prague, Donald Knuth, Isaac Newton, Larry Wall, P = NP, Paul Graham, Perl 6, slashdot, SpamAssassin



pages: 968 words: 224,513

The Art of Assembly Language by Randall Hyde

Donald Knuth, P = NP, p-value, sorting algorithm, Von Neumann architecture, Y2K


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, Bill Joy: nanobots, Black Swan, carbon-based life, 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, feminist movement, framing effect, friendly AI, Georg Cantor, global pandemic, global village, Gödel, Escher, Bach, hindsight bias, Intergovernmental Panel on Climate Change (IPCC), invention of agriculture, Kevin Kelly, Kuiper Belt, Law of Accelerating Returns, life extension, means of production, meta analysis, meta-analysis, Mikhail Gorbachev, millennium bug, mutually assured destruction, nuclear winter, P = NP, peak oil, phenotype, planetary scale, Ponzi scheme, prediction markets, RAND corporation, Ray Kurzweil, reversible computing, Richard Feynman, Ronald Reagan, scientific worldview, Singularitarianism, social intelligence, South China Sea, strong AI, superintelligent machines, supervolcano, technological singularity, technoutopianism, The Coming Technological Singularity, Tunguska event, twin studies, 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, Arthur Eddington, artificial general intelligence, availability heuristic, Bayesian statistics, Berlin Wall, Build a better mousetrap, Cass Sunstein, cellular automata, cognitive bias, cognitive dissonance, correlation does not imply causation, cosmological constant, creative destruction, Daniel Kahneman / Amos Tversky, dematerialisation, different worldview, discovery of DNA, Douglas Hofstadter, Drosophila, effective altruism, experimental subject, Extropian, friendly AI, fundamental attribution error, Gödel, Escher, Bach, hindsight bias, index card, index fund, Isaac Newton, John Conway, John von Neumann, Long Term Capital Management, Louis Pasteur, mental accounting, meta analysis, meta-analysis, money market fund, Nash equilibrium, Necker cube, NP-complete, P = NP, pattern recognition, Paul Graham, 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, Solar eclipse in 1919, speech recognition, statistical model, Steven Pinker, strong AI, technological singularity, The Bell Curve by Richard Herrnstein and Charles Murray, the map is not the territory, the scientific method, Turing complete, Turing machine, ultimatum game, X Prize, Y Combinator, zero-sum game