# P = NP

18 results back to index

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

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

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.

The Simpsons and Their Mathematical Secrets by Simon Singh

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

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.

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

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

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

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

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.

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

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

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.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 for (a, b) in word_tag_pairs if b == '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.

Python for Finance by Yuxing Yan

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

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 for q in x] closes = [q 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]=='a': t= datetime.datetime.fromtimestamp(int(p[i].replace('a',''))) date.append(t) else: date.append(t+datetime.timedelta(minutes =int(p[i]))) [ 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.

The Wrecking Crew: How Conservatives Rule by Thomas Frank

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

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

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

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.

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

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

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.

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

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

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 speciﬁcally: k − µ − 12 k − µ + 12 − Pr[B(n; p) = k] ≈ σ σ 2.2.2.3 Student distribution The Student distribution, with n degrees of freedom, is deﬁned by the density −(ν+1)/2 ) ( ν+1 x2 2 1+ f (x) = √ ν ( ν2 ) νπ +∞ In this expression, the gamma function is deﬁned 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

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.

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

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

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.

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

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

\$#\$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 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) = @{\$_}; my \$tparses = \$T->(\$input1); transform { my (\$tv, \$input2) = @{\$_}; [[\$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) = @{\$_}; [\$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.

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

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

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

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?

The Transhumanist Reader by Max More, Natasha Vita-More

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

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

. | 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. pages: 1,737 words: 491,616

Rationality: From AI to Zombies by Eliezer Yudkowsky

Or rather, I don’t always advocate that human beings, trying to solve their problems, should try to make up verbal probabilities, and then apply the laws of probability theory or decision theory to whatever number they just made up, and then use the result as their final belief or decision. The laws of probability are laws, not suggestions, but often the true Law is too difficult for us humans to compute. If P ≠ NP and the universe has no source of exponential computing power, then there are evidential updates too difficult for even a superintelligence to compute—even though the probabilities would be quite well-defined, if we could afford to calculate them. So sometimes you don’t apply probability theory. Especially if you’re human, and your brain has evolved with all sorts of useful algorithms for uncertain reasoning, that don’t involve verbal probability assignments.