P = NP

17 results back to index


pages: 236 words: 50,763

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

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Andrew Wiles, Claude Shannon: information theory, cloud computing, complexity theory, Erdős number, four colour theorem, Gerolamo Cardano, Isaac Newton, John von Neumann, linear programming, new economy, NP-complete, Occam's razor, P = NP, Paul Erdős, Richard Feynman, Richard Feynman, smart grid, Stephen Hawking, traveling salesman, Turing machine, Turing test, Watson beat the top human players on Jeopardy!, William of Occam

Cryptography If P = NP What would happen to cryptography if we were in the “beautiful world” of chapter 2 where P = NP? We could easily compute whether 5,754,853,343 and 2,860,486,313 were prime numbers and that 5,754,853,343 × 2,860,486,313 = 16,461,679,220,973,794,359. We could even do these computations for numbers that were thousands or millions of digits long. Since we would be able to verify the solution to a factoring problem, the factoring problem would sit in NP. If P = NP, then factoring would now be computationally efficient, and we could find the prime factors of numbers that are millions of digits long. P = NP would break the RSA protocol. P = NP breaks all public-key protocols, for if P = NP, you can always recover the private key from the public key. If P = NP, it is impossible to send secret messages to someone you have never communicated with before.

We have seen some small progress with circuits using non-“natural” techniques building on the paradox ideas talked about earlier in this chapter. But hope for a solution to P versus NP by showing an NP problem requires large circuits has dimmed considerably. How Not to Prove P ≠ NP On August 6, 2010, Vinay Deolalikar, a research scientist at Hewlett-Packard Labs, sent to twenty-two leading theoretical computer scientists a copy of his paper, titled simply “P ≠ NP.” Many people, dreaming of fame and fortune (the million-dollar bounty from the Clay Mathematics Institute), have come up with “proofs” that settle the P versus NP problem, claiming to show P ≠ NP, or P = NP, or that it is impossible to determine whether or not P = NP, or that the P versus NP question doesn’t even make sense. Every year dozens of these manuscripts are emailed to computer scientists, submitted to academic journals, and posted on the Internet.

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.

 

pages: 262 words: 65,959

The Simpsons and Their Mathematical Secrets by Simon Singh

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Albert Einstein, Andrew Wiles, Benoit Mandelbrot, cognitive dissonance, Erdős number, Georg Cantor, Grace Hopper, Isaac Newton, John Nash: game theory, mandelbrot fractal, Menlo Park, Norbert Wiener, P = NP, Paul Erdős, probability theory / Blaise Pascal / Pierre de Fermat, Richard Feynman, Richard Feynman, Schrödinger's Cat, Simon Singh, Stephen Hawking, Wolfskehl Prize, women in the workforce

In turn, this would jeopardize the security of everything from personal online purchases to high-level international political and military communications. The problem is often summarized as “P = NP or P ≠ NP?”, which asks the question: Will apparently difficult problems (NP) one day be shown to be just as easy as simple problems (P), or not? Finding the solution to the mystery of P = NP or P ≠ NP? is on the mathematicians’ most wanted list, and there is even a prize on its head. The Clay Mathematics Institute, established in Cambridge, Massachusetts, by the philanthropist Landon Clay, listed this puzzle as one of its seven Millennium Prize Problems in 2000, offering a $1 million reward for a definitive answer to the question P = NP or P ≠ NP? David S. Cohen, who explored P-type and NP-type problems while studying for his master’s degree in computer science at the University of California, Berkeley, has a hunch that NP-type problems are indeed much easier than we currently think, which is why P = NP appears behind Homer in his 3-D universe.

Cohen, who explored P-type and NP-type problems while studying for his master’s degree in computer science at the University of California, Berkeley, has a hunch that NP-type problems are indeed much easier than we currently think, which is why P = NP appears behind Homer in his 3-D universe. However, Cohen holds a minority view. When William Gasarch, a computer scientist at the University of Maryland, polled one hundred researchers in 2002, only 9 percent thought that P = NP, while 61 percent favored P ≠ NP. He repeated the poll in 2010, and this time 81 percent favored P ≠ NP. Of course, truth in mathematics is not decided by a popularity contest, but if the majority turn out to be right, then Cohen’s positioning of P = NP in the landscape of “Homer3” will look somewhat incongruous. This, however, should not prove to be an issue in the short term, as half of the mathematicians polled did not think that the problem would be resolved during this century.

Just before Homer’s universe disappears, Cohen dangles a particularly intriguing mathematical morsel for the discerning viewer. In the scene shown here, a slightly unusual arrangement of Euler’s equation is visible over Homer’s left shoulder. This equation also appears in “MoneyBART.” Finally, in the same image, the relationship P = NP can be seen over Homer’s right shoulder. Although the majority of viewers would not have noticed these three letters, let alone given them a second thought, P = NP represents a statement about one of the most important unsolved problems in theoretical computer science. P = NP is a statement concerning two types of mathematical problems. P stands for polynomial and NP for nondeterministic polynomial. In crude terms, P-type problems are easy to solve, while NP-type problems are difficult to solve, but easy to check. For example, multiplication is easy and so is classified as a P-type problem.

 

pages: 523 words: 143,139

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

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

4chan, Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, algorithmic trading, anthropic principle, asset allocation, autonomous vehicles, Berlin Wall, Bill Duvall, bitcoin, Community Supported Agriculture, complexity theory, constrained optimization, cosmological principle, cryptocurrency, Danny Hillis, delayed gratification, dematerialisation, diversification, 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, John Nash: game theory, John von Neumann, knapsack problem, Lao Tzu, linear programming, martingale, Nash equilibrium, natural language processing, NP-complete, P = NP, packet switching, prediction markets, race to the bottom, RAND corporation, RFC: Request For Comment, Robert X Cringely, sealed-bid auction, second-price auction, self-driving car, Silicon Valley, Skype, sorting algorithm, spectrum auction, Steve Jobs, stochastic process, Thomas Malthus, traveling salesman, Turing machine, urban planning, Vickrey auction, Walter Mischel, Y Combinator

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 question of whether P = NP (i.e., whether it’s possible to jump efficiently to the solutions of NP problems) is the greatest unsolved mystery in computer science. The main advance toward a solution has been the demonstration that there are certain problems with a special status: if one of them can be solved efficiently, then any problem in NP can be solved efficiently and P = NP (Cook, “The Complexity of Theorem-Proving Procedures”). These are known as “NP-hard” problems. In the absence of an answer to whether P = NP, problems in NP cannot be solved efficiently, which is why we refer to them as “intractable.” (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.

This function is intimately related to the distribution of prime numbers, and in particular how regularly those numbers appear on the number line. If the hypothesis is true, then primes are well enough behaved as to guarantee the efficiency of Miller’s algorithm. But nobody knows if it’s true. In fact, the Riemann hypothesis is one of six major open problems in mathematics for whose solutions the Clay Mathematics Institute will award a “Millennium Prize” of $1 million. The question of whether P = NP, which we saw in chapter 8, is also a Millennium Prize problem.) “Michael, this is Vaughan”: Rabin tells this story in Shasha and Lazere, Out of Their Minds. quickly identify even gigantic prime numbers: Rabin’s paper on his primality test, “Probabilistic Algorithm for Testing Primality,” appeared a few years later. In parallel, Robert Solovay and Volker Strassen had developed a similar probabilistic algorithm based on a different set of equations that primes need to obey, although their algorithm was less efficient; see Solovay and Strassen, “A Fast Monte-Carlo Test for Primality.”

 

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

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

airport security, Alfred Russel Wallace, Amazon Mechanical Turk, Berlin Wall, Black Swan, book scanning, Cass Sunstein, 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, 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, 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

John Heywood, Dies at 37,” MIT News, November 28, 2006, http://web.mit.edu/newsoffice/2006/obit-heywood.html. 32 Hawkins’s dissertation was on recognizing handwriting, so he had the satisfaction of seeing that work successfully commercialized in the Palm Pilot that he invented. 33 Interview with the author, October 25, 2010. 34 Alexia Tsotsis, “Attempt at P ≠ NP Proof Gets Torn Apart Online,” August 12, 2010, TechCrunch, http://techcrunch.com/2010/08/12/fuzzy-math/. See also Vinay Deolalikar’s blog at http://www.hpl.hp.com/personal/Vinay_Deolalikar/. 35 Tsotsis, “Attempt at P ≠ NP Proof Gets Torn Apart Online.” 36 Richard Smith, “The Power of the Unrelenting Impact Factor—Is It a Force for Good or Harm?” International Journal of Epidemiology 35, no. 5: 1129–1120, DOI:10.1093/ije/dyl191, http://ije.oxfordjournals.org/cgi/content/full/35/5/1129. 37 Ibid. 38 Interview with Victor Henning, August 18, 2010. 39 The number of active users and nonduplicated articles is, of course, lower. 40 Interview with Peter Binfield, October 8, 2009. 41 Interview with Jean-Claude Bradley, August 25, 2010. 42 The UsefulChem blog is at http://usefulchem.blogspot.com/.

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.

 

pages: 504 words: 89,238

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

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

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

You can see that these recipes are extremely simple; in each case, we use the string concatenation operation + to splice the values for the child constituents to make a value for the parent constituent. 362 | Chapter 10: Analyzing the Meaning of Sentences >>> nltk.data.show_cfg('grammars/book_grammars/sql0.fcfg') % start S S[SEM=(?np + WHERE + ?vp)] -> NP[SEM=?np] VP[SEM=?vp] VP[SEM=(?v + ?pp)] -> IV[SEM=?v] PP[SEM=?pp] VP[SEM=(?v + ?ap)] -> IV[SEM=?v] AP[SEM=?ap] NP[SEM=(?det + ?n)] -> Det[SEM=?det] N[SEM=?n] PP[SEM=(?p + ?np)] -> P[SEM=?p] NP[SEM=?np] AP[SEM=?pp] -> A[SEM=?a] PP[SEM=?pp] NP[SEM='Country="greece"'] -> 'Greece' NP[SEM='Country="china"'] -> 'China' Det[SEM='SELECT'] -> 'Which' | 'What' N[SEM='City FROM city_table'] -> 'cities' IV[SEM=''] -> 'are' A[SEM=''] -> 'located' P[SEM=''] -> 'in' This allows us to parse a query into SQL: >>> from nltk import load_parser >>> cp = load_parser('grammars/book_grammars/sql0.fcfg') >>> query = 'What cities are located in China' >>> trees = cp.nbest_parse(query.split()) >>> answer = trees[0].node['sem'] >>> q = ' '.join(answer) >>> print q SELECT City FROM city_table WHERE Country="china" Your Turn: Run the parser with maximum tracing on, i.e., cp = load_parser('grammars/book_grammars/sql0.fcfg', trace=3), and examine how the values of SEM are built up as complete edges are added to the chart.

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.

 

pages: 408 words: 85,118

Python for Finance by Yuxing Yan

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

asset-backed security, 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

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: 482 words: 122,497

The Wrecking Crew: How Conservatives Rule by Thomas Frank

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

affirmative action, anti-communist, barriers to entry, Berlin Wall, Bernie Madoff, British Empire, 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, 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: 396 words: 117,149

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

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

3D printing, Albert Einstein, Amazon Mechanical Turk, Arthur Eddington, Benoit Mandelbrot, bioinformatics, Black Swan, Brownian motion, cellular automata, Claude Shannon: information theory, combinatorial explosion, computer vision, constrained optimization, correlation does not imply causation, 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 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, P = NP, PageRank, pattern recognition, phenotype, planetary scale, pre–internet, random walk, Ray Kurzweil, recommendation engine, Richard Feynman, Richard Feynman, Second Machine Age, self-driving car, Silicon Valley, speech recognition, statistical model, Stephen Hawking, Steven Levy, Steven Pinker, superintelligent machines, the scientific method, The Signal and the Noise by Nate Silver, theory of mind, transaction costs, Turing machine, Turing test, Vernor Vinge, Watson beat the top human players on Jeopardy!, white flight

Who would have guessed that all these problems, superficially so different, are really the same? But if they are, it makes sense that one algorithm could learn to solve all of them (or, more precisely, all efficiently solvable instances). P and NP are the two most important classes of problems in computer science. (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?

Benoît Mandelbrot explores the fractal geometry of nature in the eponymous book* (Freeman, 1982). James Gleick’s Chaos (Viking, 1987) discusses and depicts the Mandelbrot set. The Langlands program, a research effort that seeks to unify different subfields of mathematics, is described in Love and Math, by Edward Frenkel (Basic Books, 2014). The Golden Ticket, by Lance Fortnow (Princeton University Press, 2013), is an introduction to NP-completeness and the P = NP problem. The Annotated Turing,* by Charles Petzold (Wiley, 2008), explains Turing machines by revisiting Turing’s original paper on them. The Cyc project is described in “Cyc: Toward programs with common sense,”* by Douglas Lenat et al. (Communications of the ACM, 1990). Peter Norvig discusses Noam Chomsky’s criticisms of statistical learning in “On Chomsky and the two cultures of statistical learning” (http://norvig.com/chomsky.html).

., 29, 137–139 Obama, Barack, 17 Objective reality, Bayesians and, 167 Occam’s razor, 77–78, 196, 300–301 OkCupid, 265, 269, 310 O’Keefe, Kevin, 206 On Intelligence (Hawkins), 28, 118 Online analytical processing, 8 Online dating, 265–266, 269, 310 Open-source movement, 45, 279, 292 Optimization, 30–31, 33, 109, 135, 239, 241, 283 constrained, 193–195 O’Reilly, Tim, 9 The Organization of Behavior (Hebb), 93 OR gate, 96 The Origin of Species (Darwin), 28, 123 OR operation, 2 Overfitting, 59, 70–75, 126, 169, 301 avoiding, 76–77 hypotheses and, 73–75 Master Algorithm and, 243 nearest-neighbor algorithm and, 183 noise and, 73 singularity and, 287 support vector machines and, 196 P = NP question, 33–34 PAC learning, 74–75 Page, Larry, 55, 154, 227 PageRank algorithm, 154, 305 PAL (Personalized Assistant that Learns) project, 255 Pandora, 171 Papadimitriou, Christos, 135 Papert, Seymour, 100–101, 102, 110, 112, 113 Parallax effect, 287 Parallel processing, 257–258 Parasites, 135 Pascal, Blaise, 63 Pattern recognition, 8. See also Machine learning Patterns in data, 70–75 PCA.

 

pages: 312 words: 35,664

The Mathematics of Banking and Finance by Dennis W. Cox, Michael A. A. Cox

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

barriers to entry, Brownian motion, call centre, correlation coefficient, inventory management, iterative process, linear programming, meta analysis, meta-analysis, P = NP, pattern recognition, random walk, traveling salesman, value at risk

Where this is not the case the normal distribution should be used with caution. 8.6 NORMAL APPROXIMATION TO THE BINOMIAL DISTRIBUTION The binomial distribution was discussed in section 7.3. Using the equations from that section, x − np could be approximated by a standard normal distribution, if x is B(n, p) then z = √ np (1 − p) for a population where n is large enough. This means that the probability that x lies in the range (a, b) can be approximated by a normal probability in the range a − 0.5 − np b + 0.5 − np , √ √ np (1 − p) np (1 − p) The factor of 0.5 is referred to as the continuity correction and makes allowance for converting from a discrete to a continuous distribution. As a general rule the approximation is employed if the variance np(1 − p) exceeds 10. 8.6.1 An example of the normal approximation to the binomial distribution A population consists of a series of deposit and lending transactions. Of 7,000 transactions, 3,682 (52.6%) were deposits.

The question then is whether the higher proportion in the sample is significantly different from the general experience. Taking p = 0.512 and n = 7,000, how likely is that the sample will contain 3,682 or more deposit transactions? The mean for the general population over time is 7,000 × 0.512 = 3,584 and the variance is 7,000 × 0.512 × 0.488 giving a standard deviation of 41.82. Using the a − 0.5 − np b + 0.5 − np expression above √ ,√ , the required probability is calculated as: np (1 − p) np (1 − p) 7,000 + 0.5 − 3,584 3,682 − 0.5 − 3,584 <z< Prob = Prob(2.331 < z < 81.692) 41.82 41.82 ≈ Prob(z < −2.331) = 0.01 This probability is small enough to suggest that the sample of 7,000 does not in fact differ from the general trend. It is then possible to identify a sample as being an outlier, but this in itself carries risks. In such cases, the only real alternative is to consider the total population and assess whether there has been a paradigm shift that needs to be considered. 8.7 NORMAL APPROXIMATION TO THE POISSON DISTRIBUTION The normal distribution can also be used to approximate the Poisson distribution, which is discussed in section 7.4.

 

pages: 416 words: 39,022

Asset and Risk Management: Risk Oriented Finance by Louis Esch, Robert Kieffer, Thierry Lopez

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

asset allocation, Brownian motion, business continuity plan, business process, capital asset pricing model, computer age, corporate governance, discrete time, diversified portfolio, implied volatility, index fund, interest rate derivative, iterative process, P = NP, p-value, random walk, risk/return, shareholder value, statistical model, stochastic process, transaction costs, value at risk, Wiener process, yield curve, zero-coupon bond

If n is the number of trials and p the probability of each success succeeding, the term used is Bernoulli scheme with parameters (n; p) and the number of successes out of the Probabilistic Concepts 351 n tests is a binomial parameter r.v., termed B(n, p). This discrete random variable takes the values 0, 1, 2, . . . , n with the following associated probabilities:5 n p k (1 − p)n−k Pr[B(n; p) = k] = k ∈ {0, 1, . . . , n} k The sum of these probabilities equals 1, in accordance with Newton’s binomial formula. In addition, the typical values for this distribution are given by: E(B(n; p)) = np var(B(n; p)) = np(1 − p) The binomial distribution allows two interesting approximations when the n parameter is large. Thus, for a very small p, we have the approximation through Poisson’s law with np parameter: (np)k Pr[B(n; p) = k] ≈ e−np k! For a p that is not √ to close to 0 or 1, the binomial r.v. tends towards a normal law with parameters (np; np(1 − p)), and more specifically: k − µ − 12 k − µ + 12 − Pr[B(n; p) = k] ≈ σ σ 2.2.2.3 Student distribution The Student distribution, with n degrees of freedom, is defined by the density −(ν+1)/2 ) ( ν+1 x2 2 1+ f (x) = √ ν ( ν2 ) νπ +∞ In this expression, the gamma function is defined by (n) = 0 e−x x n−1 dx.

 

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

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

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 process, buy low sell high, capital asset pricing model, centre right, collateralized debt obligation, corporate governance, correlation coefficient, Credit Default Swap, credit default swaps / collateralized debt obligations, currency manipulation / currency intervention, discounted cash flows, disintermediation, diversification, 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, Nick Leeson, P = NP, pattern recognition, 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 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

My advisor and others established that for a huge variety of generic problems, there are algorithms that check proposed solutions in time, 227 JWPR007-Lindsey 228 May 7, 2007 17:9 h ow i b e cam e a quant which is a polynomial function of the number of variables. Yet the bestknown algorithms for actually finding solutions to such problems run in time, which is exponential in the number of variables. Furthermore, if any of the generic problems have a polynomial time algorithm for finding solutions, then they all do: Hence, Cook’s famous conjecture that there is no such algorithm, i.e., P = NP.1 Unfortunately, the only problems I found interesting were too hard, or at least too hard for me (a good sign that one is in the wrong field). I wasn’t getting anywhere, and my money had run out. As a foreign (Australian) student in Canada, I wasn’t permitted to work outside the university. So when the finance department at the University of Toronto advertised for a computer programmer on the intranet, I jumped at it despite my ignorance of finance.

He cracked up, and I’ve been vainly (in both senses of that word) repeating this story to people for years in hopes of a repeat reaction. Sadly my mortality rate on this one is quite high. 22. This might be less true for some quantitative asset allocation portfolios, like some of the strategies we run, but the general point still holds. Chapter 16 1. The first person to settle this conjecture will win a $1 million; the P = NP conjecture is one of the seven Clay Mathematics Institute Millennium problems. So it is (barely) possible to make money in mathematics without moving to finance! http://www.claymath.org/ millennium/. 2. Conventional finance implausibly assumes that each person has a utility function and seeks to maximize it. Normative portfolio theory is concerned with the properties of utility functions and prescribes utility functions that achieve specified long-term goals such as maximizing the expected rate of compound return.

 

pages: 661 words: 187,613

The Language Instinct: How the Mind Creates Language by Steven Pinker

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Albert Einstein, cloud computing, David Attenborough, double helix, Drosophila, elephant in my pajamas, finite state, illegal immigration, Loebner Prize, Maui Hawaii, meta analysis, meta-analysis, natural language processing, out of africa, P = NP, phenotype, rolodex, Ronald Reagan, Saturday Night Live, speech recognition, Steven Pinker, theory of mind, transatlantic slave trade, Turing machine, Turing test, Yogi Berra

The best way to appreciate how understanding works is to trace the parsing of a simple sentence, generated by a toy grammar like the one of Chapter 4, which I repeat here: S NP VP “A sentence can consist of a noun phrase and a verb phrase.” NP (det) N (PP) “A noun phrase can consist of an optional determiner, a noun, and an optional prepositional phrase.” VP VNP(PP) “A verb phrase can consist of a verb, a noun phrase, and an optional prepositional phrase.” PP P NP “A prepositional phrase can consist of a preposition and a noun phrase.” N boy, girl, dog, cat, ice cream, candy, hotdogs “The nouns in the mental dictionary include boy, girl,…” V eats, likes, bites “The verbs in the mental dictionary include eats, likes, bites.” P with, in, near “The prepositions include with, in, near.” det a, the, one “The determiners include a, the, one.”

And grammatical devices designed for communicating precise information about time, space, objects, and who did what to whom are not like the proverbial thermonuclear fly-swatter. Recursion in particular is extremely useful; it is not, as Premack implies, confined to phrases with tortuous syntax. Without recursion you can’t say the man’s hat or I think he left. Recall that all you need for recursion is an ability to embed a noun phrase inside another noun phrase or a clause within a clause, which falls out of rules as simple as “NP det N PP” and “PP P NP.” With this ability a speaker can pick out an object to an arbitrarily fine level of precision. These abilities can make a big difference. It makes a difference whether a far-off region is reached by taking the trail that is in front of the large tree or the trail that the large tree is in front of. It makes a difference whether that region has animals that you can eat or animals that can eat you.

 

pages: 525 words: 149,886

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

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Defenestration of Prague, Isaac Newton, P = NP, Paul Graham, slashdot, SpamAssassin

$#$wanted) { next unless defined $wanted->[$i]; unless ($wanted->[$i] eq $next->[$i]) { return undef; } } my $wanted_value = $value->($next, $u); return single([$wanted_value, tail($input)]); }; $N{$parser} = "[@$wanted]"; return $parser; } Similarly, End_of_input() and nothing() return singleton streams when they succeed: sub End_of_Input { my $input = shift; defined($input) ? () : single(["EOI", undef]); } sub nothing { my $input = shift; return single([undef, $input]); } alternate() becomes much simpler; it’s merely a call to union() to join together the streams returned by its argument parsers: sub alternate { my @p = @_; return parser { return undef } if @p == 0; return $p[0] if @p == 1; my $p; $p = parser { my $input = shift; union(map $_->($input), @p); }; $N{$p} = "(" . join(" | ", map $N{$_}, @p) . ")"; return $p; } concatenate(), however, is trickier. To concatenate parsers S and T, we must first call S on the main input, returning a stream of [$svalue, $input1] pairs. We then call T on each of the $input1 values, producing a stream of [$tvalue, $input2] pairs. The parser produced by concatenate() then produces a stream of [[$svalue, $tvalue], $input2] pairs for each $tvalue and its corresponding $svalue: sub concatenate2 { my ($S, $T) = @_; my $p; $p = parser { my $input = shift; my $sparses = $S->($input); sunion( transform { my ($sv, $input1) = @{$_[0]}; my $tparses = $T->($input1); transform { my ($tv, $input2) = @{$_[0]}; [[$sv, $tv], $input2]; } $tparses; } $sparses ); }; $N{$p} ="@N{$S, $T}"; return $p; } This concatenates only two parsers; to concatenate more than two, we repeat the process as necessary: sub concatenate { my @p = @_; return \&null if @p == 0; my $p = shift @p; return $p if @p == 0; my $result = concatenate2( $p, concatenate(@p) ); $N{$result} = "@N{$p, @p}"; return $result; } Finally, T needs to be changed to apply its transformation function to each of the values returned by its argument parser: sub T{ my ($parser, $transform) = @_; my $p = parser { my $input = shift; transform { my ($v, $input1) = @{$_[0]}; [$transform->($v), $input1]; } $parser->($input); }; $N{$p} = $N{$parser}; return $p; } 8.9 Overloading The recursive-descent parsing system works well, and it’s easy to compose small parsers into bigger ones and to capture common patterns in larger parser-generating functions, such as operator() of Section 8.4.4.

 

pages: 496 words: 154,363

I'm Feeling Lucky: The Confessions of Google Employee Number 59 by Douglas Edwards

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Albert Einstein, AltaVista, Any sufficiently advanced technology is indistinguishable from magic, barriers to entry, book scanning, Build a better mousetrap, Burning Man, business intelligence, call centre, crowdsourcing, don't be evil, Elon Musk, fault tolerance, Googley, gravity well, invisible hand, Jeff Bezos, job-hopping, Menlo Park, microcredit, music of the spheres, Network effects, P = NP, PageRank, performance metric, pets.com, Ralph Nader, risk tolerance, second-price auction, side project, Silicon Valley, Silicon Valley startup, slashdot, stem cell, Superbowl ad, Y2K

Our arrogance ultimately became a nasty undertone in conversations about Google taking place in the press and among those trying to do business with us, but I rarely saw it expressed by Googlers toward their own colleagues. When Googlers did engage in blatant opinioneering, they did it on Googlers-MISC,* the Las Vegas of mailing lists, where nothing was out of bounds. On MISC, Googlers offered theories about proving P=NP and the best way to levitate frogs. They debated the brand of bottled water Charlie should stock in the micro-kitchens, a discussion encompassing total dissolved solids, bottle size, and the health benefits of naturally occurring uranium. After a week of this, Charlie's patience wore thin enough that he threatened to pull all the bottles and let the staff drink pond water. I started a rancorous MISC thread by suggesting we eliminate the free donuts Ed Karrels delivered on Fridays in favor of fresh bagels.

 

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

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Albert Einstein, Eratosthenes, Georg Cantor, P = NP

Exercise 2.35 Use Russell’s recipe to translate the following sentences: 1. The King is not raging. 2. The King is loved by all his subjects. (use K(x) for ‘x is a King’, and S(x, y) for ‘x is a subject of y’). Exercise 2.36 Translate the following logical statements back into English. 1. ∃x ∈ R(x2 = 5). 58 CHAPTER 2. TALKING ABOUT MATHEMATICAL OBJECTS 2. ∀n ∈ N∃m ∈ N(n < m). 3. ∀n ∈ N¬∃d ∈ N(1 < d < (2n + 1) ∧ d|(2n + 1)). 4. ∀n ∈ N∃m ∈ N(n < m ∧ ∀p ∈ N(p 6 n ∨ m 6 p)). 5. ∀ε ∈ R+ ∃n ∈ N∀m ∈ N(m > n ⇒ (|a − am | 6 ε)). (R+ is the set of positive reals; a, a0 , a1 , . . . refer to real numbers .) Remark. Note that translating back and forth between formulas and plain English involves making decisions about a domain of quantification and about the predicates to use. This is often a matter of taste. For instance, how does one choose between P (n) for ‘n is prime’ and the spelled out n > 1 ∧ ¬∃d ∈ N(1 < d < n ∧ d|n), which expands the definition of being prime?

 

pages: 798 words: 240,182

The Transhumanist Reader by Max More, Natasha Vita-More

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

23andMe, Any sufficiently advanced technology is indistinguishable from magic, artificial general intelligence, augmented reality, Bill Joy: nanobots, bioinformatics, brain emulation, Buckminster Fuller, cellular automata, clean water, cloud computing, cognitive bias, cognitive dissonance, combinatorial explosion, conceptual framework, Conway's Game of Life, cosmological principle, data acquisition, discovery of DNA, Drosophila, en.wikipedia.org, experimental subject, Extropian, fault tolerance, Flynn Effect, Francis Fukuyama: the end of history, Frank Gehry, friendly AI, game design, germ theory of disease, hypertext link, impulse control, index fund, John von Neumann, joint-stock company, Kevin Kelly, Law of Accelerating Returns, life extension, Louis Pasteur, Menlo Park, meta analysis, meta-analysis, moral hazard, Network effects, Norbert Wiener, P = NP, pattern recognition, phenotype, positional goods, prediction markets, presumed consent, Ray Kurzweil, reversible computing, RFID, Richard Feynman, Ronald Reagan, silicon-based life, Singularitarianism, stem cell, stochastic process, superintelligent machines, supply-chain management, supply-chain management software, technological singularity, Ted Nelson, telepresence, telepresence robot, telerobotics, the built environment, The Coming Technological Singularity, the scientific method, The Wisdom of Crowds, transaction costs, Turing machine, Turing test, Upton Sinclair, Vernor Vinge, Von Neumann architecture, Whole Earth Review, women in the workforce

It seems to me that what these and many other examples show is that we can gain a great deal of insight into the limitations of future technologies, without necessarily being able to say in detail what those technologies are. At a higher level of abstraction, we have very little understanding of what classes of computational problems can be efficiently solved. For example, virtually none of the important computational complexity problems (such as P ! = NP ! = PSPACE) in computer science have been resolved. Resolving some of these problems will give us insight into what types of problems are solvable or not solvable by a Dominant AI. Indeed, computer science recently has provided some insight into what constraints a Dominant AI will face. There is a problem in computer science known as “Succinct Circuit Value.” It has been proven that this problem cannot be solved efficiently, either on a classical computer, or even on a quantum computer.

 

The Art of Computer Programming by Donald Ervin Knuth

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Brownian motion, complexity theory, correlation coefficient, Eratosthenes, 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

. | A major part of this calculation could be made noticeably faster if q (instead of j) were tested against M in step S4, and if a new loop were appended that outputs 2j + 1 for all remaining X[j] that equal 1, suppressing the manipulation of p and q. 4.5.4 ANSWERS TO EXERCISES 659 Notes: The original sieve of Eratosthenes was described in Book 1, Chapter 13 of Nicomachus's Introduction to Arithmetic. It is well known that 5Zpprime[p < N]/p = lnlnJV + M + O((logiV)-10000), where M = 7 + Efe>2 A*(fc) lnC(fc)/fc is Mertens's constant 0.26149 72128 47642 78375 54268 38608 69585 90516-; see F. Mertens, Crelle 76 A874), 46-62; Greene and Knuth, Mathematics for the Analysis of Algorithms (Boston: Birkhauser, 1981), §4.2.3. In particular, the number of operations in the original algorithm described by Nicomachus is iVlnlnN + O(N). Improvements in the efficiency of sieve methods for generating primes are discussed in exercise 5.2.3-15 and in Section 7.1. 9.