P vs NP

6 results back to index

The Road to Conscious Machines by Michael Wooldridge

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

The theory of NP-completeness was developed in the 1970s, and in this time many AI problems were discovered to be NP-complete. See also P vs NP problem. ontological engineering In an expert system (and, more generally, in a knowledge-based system), this is the task of defining the conceptual vocabulary you will use to represent knowledge in your system. opaqueness (of neural nets) The problem is that the expertise a neural network has is encoded in a series of numeric weights: we have no way of being able to tell what those weights ‘mean’. This means that current neural nets can’t explain or justify their decisions. P vs NP problem The question of whether NP-complete problems definitely can or cannot always be solved efficiently.

…

If you could find a quick recipe for solving just one NP-complete problem, then you would also have found a quick recipe for solving all of them. But, to date, nobody has found an efficient recipe for any NP-complete problem. And the question of whether NP-complete problems can be efficiently solved is, in fact, one of the most important open problems in science today. It is known as the P vs NP problem,17 and if you can settle it one way or the other to the satisfaction of the scientific community, you stand to receive a prize of one million dollars from the Clay Mathematics Institute, who in the year 2000 identified it as one of the ‘Millennium Problems’ in mathematics. Smart money says that NP-complete problems cannot be solved efficiently; but smart money also says that we are a long way from knowing for certain whether this really is the case.

…

P vs NP problem The question of whether NP-complete problems definitely can or cannot always be solved efficiently. One of the biggest open problems in mathematics today. Not likely to be settled any time soon. (‘P’ stands for ‘polynomial time’; ‘NP’ stands for ‘non-deterministic polynomial time’: technically, the P vs NP problem is whether problems that can be solved in non-deterministic polynomial time can be solved in polynomial time.) perception The process of understanding what is around you in your environment. This was a fundamental sticking point for symbolic AI. perceptron, perceptron model A type of neural net, studied in the 1960s but still relevant today.

Journey to the Edge of Reason: The Life of Kurt Gödel by Stephen Budiansky

Abraham Wald, Albert Einstein, anti-communist, business cycle, Douglas Hofstadter, fear of failure, Fellow of the Royal Society, four colour theorem, Georg Cantor, Gregor Mendel, Gödel, Escher, Bach, John von Neumann, laissez-faire capitalism, P = NP, P vs NP, Paul Erdős, rent control, scientific worldview, the scientific method, Thorstein Veblen, Turing machine, urban planning

In his last letter to von Neumann he expressed blithe confidence in his friend’s imminent and complete recovery, before going on to pose what would be one of the most fundamental questions of computer science. Gödel’s letter to his dying colleague was apparently the very first formulation of the so-called “P vs. NP” problem, which offered a striking analogy of his Incompleteness Theorem to the field of computing. “P” is the set of problems easy to solve, for example multiplication and addition. “NP” is the set of problems for which an efficient algorithm exists for checking a given solution, but finding the solution may or may not be easy, such as factoring a large number, solving a sudoku puzzle, or discovering a proof for a formula.61 Gödel pointed out that one could readily build a machine that works through every possible series of proof steps to discover whether a proof of n steps exists for a given formula.

…

., 247 Nöbeling, Georg, 102 non-constructive proofs, 113–14 Notre Dame University, 184, 185, 188–90, 192, 199–200 number theory, 69, 70–71, 121, 127, 129, 136, 144, 279 objects, mathematical, 93, 124, 240, 241, 266 obsessive-compulsive personality disorder, 169 O’Hara, John Francis, 185, 188, 189 Old Catholics, 49 ontological proof, 268–69 Oppenheim, Paul, 216 Oppenheimer, J. Robert, 237–38, 247–48, 249, 251 Orient Express, 145 P vs. NP problem, 258 Palace of Justice attack, 86, 87 Palacký, František, 17–18 paradoxes Incompleteness Theorem and, 130, 135, 267 set theory and, 109–10, 111, 130, 244, 266, 267 time travel and, 226 paranoid personality disorder, 169 parapsychology, 66 Paris, Jeff, 279 Paris KG’s visits to, 171, 188, 190, 302 n 64 mathematical congress at, 78–79 Paris Peace Conference, 51, 53–54 Pauley, Bruce B., 82 Pauli, Wolfgang, 170, 239 Peano Arithmetic, 279 Philosophers’ Staircase, 67, 180, 181 philosophy Catholic, 199, 261 idealist, 227, 242, 266 KG’s view of state of, 242 language and, 93, 95–96, 98, 100–101 logic in, 93–94, 242, 268–69 Nazis and, 183–84 scientific worldview and, 37, 70, 74, 89, 95 of time, 225–27 “physicalism,” 93 physics “Jewish science” in, 189, 202 KG’s study of, 69–70, 71, 72–73, 75 pi, 114 Plato, 112 Platonism, mathematical, 100, 239–41 Plattner, Friedrich, 202 Polgar, Alfred, 194–95 Popper, Karl, 73, 75, 88, 185–86 Porges, Otto, 168 Porkert, Adele.

…

Oswald), 155 Veblen, Oswald background and character, 150–51 European scientists recruited by, 144–45, 153, 156 Fine Hall construction and, 151–52 IAS founding and, 150, 152–53, 210 KG and, 144–45, 158, 165, 171–72, 177, 189, 208, 234 also mentioned, 143, 168, 174, 198, 221 Veblen, Thorstein, 150 Venice, 160, 190 Versailles Treaty, 53 Vienna architecture, 22–24, 23, 35 civic improvements, 22–25 coffeehouses, 11, 27, 36, 64–65, 64, 73, 90, 99, 100, 121, 122, 139 crackpot ideas in, 66 cultural center of Austria, 9–11, 15 discussion circles in, 89 housing, 31, 62, 64, 187 intellectual life, 25–26, 30, 35–37, 65–67, 89, 161 Jews and anti-Semitism in, 11, 28–30, 33–35, 194–97 political tensions in, 33–35, 62–64, 81, 86–87 population, 28, 31 Second World War and, 227, 228–29 social problems, 31–34 see also Austria; University of Vienna Vienna Academy of Sciences, 133 Vienna Circle conservatives’ attacks on, 161–62, 182 founding and origins, 73–74, 88 KG’s association with, 88, 90, 92–93, 100–1 meetings and membership, 88–91 name, origin of, 95 philosophical ideas, 93–96, 98–100 public outreach, 95, 120–21, 161 unwinding of, 161–62, 184, 208 Vienna Opera, 24, 66 Vienna Secession, 36 Vietnam War, 248, 271 visas, issuance of, 196, 200, 201, 204 Volkshochschule, 64, 261 Voltaire, 244, 245 von Kármán, Theodor, 27, 236 von Laue, Max, 62 von Mises, Richard, 89, 120 von Neumann, John, 157 background and personality, 27, 132, 156–58 computer architecture and, 116 game theory and, 219 IAS position, 150, 152 Incompleteness Theorem and, 121, 132–34 KG dictates Continuum Hypothesis result to, 177, 190 KG’s career, advocacy and support for, 106, 189, 201, 234, 238–39, 248 Morgenstern and, 219 P vs. NP problem and, 258 paralysis and death, 258, 274 also mentioned, 192, 236, 244 von Neumann, Klári, 147, 151, 156, 157 von Schönerer, Georg, 34 Wagner, Richard, 255 Wagner-Jauregg, Julius, 168, 172 Waismann, Friedrich, 88, 100, 101, 120, 121, 185, 192 Wald, Abraham, 102, 163–64, 185, 275 Wallace, Henry, 246 Wang, Hao on KG’s conscientiousness and precision, 75, 170 on KG’s friendships, 214–15 and KG’s last days, 275–76 and KG’s philosophical ideas, 242, 265 on KG’s rational optimism, 255 Was nicht im Baedeker Steht, 82 Washington, D.C., 159, 230, 273 Washington Academy of Science, 159 Weber, Max, 82 Weil, André, 249 Wengenroth, Stow, 218 Weyl, Hermann, 110, 150, 152, 173, 236, 248 “white Jews,” 189 White Mountains, New Hampshire, 252 Whitehead, Alfred North, 74, 93, 108, 111, 121, 127, 281 Whitney, Hassler, 249 Wigderson, Avi, 278–79 William James Lectures, 170 Wilson, Woodrow, 51 Wittgenstein, Ludwig, 95 family background and personality, 24, 29, 96–100, 187 foundations of mathematics and, 112, 113, 114, 121 Hitler and, 96 KG and, 98, 101, 187 Russell and, 96–98 Schlick and, 98–100, 101 Vienna Circle and, 73, 95–96, 98–101 work as schoolteacher, 30, 99 Woolf, Harry, 276 World Almanac, The, 72, 232 World War I.

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

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

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. Unfortunately, within two days, Deolalikar’s paper suffered the fate of prior attempts. As the blog TechCrunch put it, “Both armchair and professional math pundits proceeded to tear it apart in comments sections and subsequent blog posts, finding major flaws.”35 The credibility of the person who first formulated the problem got Deolalikar’s paper circulated, but the critiquing of it occurred without much regard for credentials.

…

See Massachusetts Institute of Technology MITRE Corporation Mobs Model-based knowledge Moderation: The WELL Moreno, Jose Luis Ortiz Morning Edition (radio program) Moynihan, Daniel Patrick Mozart Effect Music Muslim surveillance Namespaces NASA National Public Radio (NPR) Nature magazine Navasky, Victor “Need to know” culture Nelson, Ted Netflix Networked knowledge Age of the Net amateur scientists book-shaped thought and characteristics of knowledge decision-making educating people in the use of Hidary’s Primary Insight hyperlinked science interdisciplinary approach to science Internet expanding possibilities for expertise Internet shaping knowledge knowledge residing in the network Linked Data Linux opening access to providing hooks for intelligence providing links for scaling knowledge scientific knowledge scientists’ generation of facts solving global social problems traditional institutions and See also Internet New York Times New Yorker magazine Nietzsche, Friedrich NOAH website Nonprofit organizations Noveck, Beth Nuclear power Nuclear war Obama, Barack birther movement building knowledge and idea networks media objectivity Open Government Initiative Objectivity in the media Oil Spill Recovery Institute Oil spills On the Origin of Species (Darwin) O’Neil, Mathieu The Onion newspaper Opacity of expertise Open filters Open Government Initiative Open access movement OpenCourseWare OpenGov site Open-notebook science Ordering the universe: humors Organizational efficiency “P vs. NP” problem “Packard Goose” (song) Page, Scott Pandora’s Hope: Essays on the Reality of Science Studies (Latour) Paper-based knowledge: stopping points for knowledge. See also Books and book publishing Paper-based tools Parenting experts Patent Office, US PatientsLikeMe.com Pavement performance Peer-review journals Perception, facts and Permission-free knowledge Philosophy defining and quantifying knowledge information overload reality unresolved knowledge Pinker, Steven Planetary Skin initiative Plato PLoS One online journal Pogue, David Polio vaccine Politics Politifact.com Popper, Karl Population growth, Malthusian theory of Pornography Postmodernism Pragmatism PressThink.org Primary Insight Principles of Geology (Lyell) Prize4Life Protein folding ProteomeCommons.org Pseudo-science Public Library of Science (PLoS) Punchcard data Pyramid, knowledge Pyramid of organizational efficiency Quora Racial/ethnic identity Ramanujan, Srinivasa RAND Corporation Random Hacks of Kindness Rauscher, Francis Raymond, Eric Reagan, Ronald Reality Reason as the path to truth and knowledge critical debate on unresolved knowledge Reliability Repositories, open access Republic of Letters Republican Party Republic.com (Sunstein) Revolution in the Middle East Rheingold, Howard Richards, Ellen Swallow Riesman, David Robustness “The Rock” (Eliot) Rogers, William Rorty, Richard Rosen, Jay Roskam, Peter Rushkoff, Douglas Russia: Dogger Bank Incident Salk, Jonas Sanger, Larry Schmidt, Michael School shootings Science amateurs in crowdsourcing expertise failures in goals of hyperlinked inflation of scientific studies interdisciplinary approaches media relations Net-based inquiry open filtering journal articles open-notebook overgeneration of scientific facts philosophical and professional differences among scientists public and private realms scientific journals transformation of scientific knowledge Science at Creative Commons Science journal Scientific journals Scientific management Scientific method Self-interest: fact-based knowledge Semantic Web Seneca Sensory overload Sexual behavior The Shallows (Carr) Shapiro, Jesse Shared experiences Shilts, Randy Shirky, Clay Shoemaker, Carolyn Simplicity in scientific thought Simulation of physical interactions Slashdot.com Sloan Digital Sky Survey Smart mobs “Smarter planet” initiative Smith, Arfon Smith, Richard Soccer Social conformity Social networks crowdsourcing expertise Middle East revolutions pooling expertise scaling social filtering Social policy: social role of facts Social reform Dickens’s antipathy to fact-based knowledge global statistical support for Bentham’s ideas Social tools: information overload Society of Professional Journalists Socrates Software defaults Software development, contests for Sotomayor, Sonia Source transparency Space Shuttle disaster Spiro, Mary Sports Sprinkle, Annie Standpoint transparency Statistics emergence of Hunch.com Stopping points for knowledge The Structure of Scientific Revolutions (Kuhn) Stupidity, Net increasing Sub-networks Suel, Gurol Sunlight Foundation Sunstein, Cass Surowiecki, James Systems biology Tag cloud Tagging Tatalias, Jean Taylor, Frederick Wilson TechCamps Technodeterminism Technology easing information overload Technorati.com Television, homophily and Temptation of hyperlinks Think tanks Thoreau, Henry David The Tipping Point (Gladwell) Todd, Mac Toffler, Alvin TopCopder Topic-based expertise Torvalds, Linus Traditional knowledge Tranche Transparency hyperlinks contributing to objectivity and of the Net Open Government Initiative Transparency and Open Government project Triangular knowledge Trillin, Calvin Trust: reliability of information Trust-through-authority system Truth elements of knowledge reason as the path to value of networked knowledge Twitter Tyme, Mae Unnailing facts Updike, John USAID UsefulChem notebook Vaccinations Verizon Vietnam Virginia Polytechnic Institute and State University Wales, Jimmy Wallace, Alfred Russel Walter, Skip Washington Post Watson, James Welch, Jack Welfare The WELL (The Whole Earth’Lectronic Link) Whole Earth Catalog Wikipedia editorial policy LA Times wikitorial experiment policymaking Virginia Tech shootings Wikswo, John Wilbanks, John Wired magazine The Wisdom of Crowds (Surowiecki) Wise crowds Wittgenstein, Ludwig Wolfram, Stephen WolframAlpha.com World Bank World Cup World War I Wurman, Richard Saul Wycliffe, John York, Jillian YourEncore Zappa, Frank Zeleny, Milan Zettabyte Zittrain, Jonathan Zuckerman, Ethan a I’m leaving this as an unsupported idea because it’s not the point of this book.

Average Is Over: Powering America Beyond the Age of the Great Stagnation by Tyler Cowen

Amazon Mechanical Turk, behavioural economics, Black Swan, brain emulation, Brownian motion, business cycle, Cass Sunstein, Charles Babbage, choice architecture, complexity theory, computer age, computer vision, computerized trading, cosmological constant, crowdsourcing, dark matter, David Brooks, David Ricardo: comparative advantage, deliberate practice, driverless car, Drosophila, en.wikipedia.org, endowment effect, epigenetics, Erik Brynjolfsson, eurozone crisis, experimental economics, Flynn Effect, Freestyle chess, full employment, future of work, game design, Higgs boson, income inequality, industrial robot, informal economy, Isaac Newton, Johannes Kepler, John Markoff, Ken Thompson, Khan Academy, labor-force participation, Loebner Prize, low interest rates, low skilled workers, machine readable, manufacturing employment, Mark Zuckerberg, meta-analysis, microcredit, Myron Scholes, Narrative Science, Netflix Prize, Nicholas Carr, off-the-grid, P = NP, P vs NP, pattern recognition, Peter Thiel, randomized controlled trial, Ray Kurzweil, reshoring, Richard Florida, Richard Thaler, Ronald Reagan, Silicon Valley, Skype, statistical model, stem cell, Steve Jobs, Turing test, Tyler Cowen, Tyler Cowen: Great Stagnation, upwardly mobile, Yogi Berra

., 188 malapropisms, 140–41 malpractice suits, 128 Malthusian wages, 136 management, 25, 27–29, 33 mandates, 237–38 Mandel, Michael, 165–66 manual labor, 56 manufacturing sector, 177 marginal costs, 182 marginal tax rates, 234 MarginalRevolution (blog), 90 Maria Theresa of Austria, 148 marketing, 11–12, 22–27, 34, 146 Marzolo, Cyril, 147 Massachusetts Institute of Technology (MIT), 37, 193, 222 master’s degrees, 37 Match Teacher Residency program, 200 Match.com, 9, 96, 98 matchmaking. See online dating mathematics and complexity of theories, 212 and division of labor, 207–8 math education, 183–84 mathematical economics, 222 “P vs. NP” problem, 101 and prodigies, 216 theorem development, 206–8 Mayhew, Henry, 33–34, 36 Mayo Clinic, 87 McAfee, Andrew, 6 McGonigal, Jane, 187 McGovern, George, 256 mechanical intelligence, 15–16, 157–58. See also artificial intelligence (AI) Mechanical Turk, 148–49 mechanization, 126–27 media, 146 median incomes, 38, 52, 60, 253 Medicaid, 234–39, 250 medical diagnosis, 87–89, 128–29 Medicare, 232–35, 237–38, 242 Medication Adherence Scores, 124 Mediterranean Europe, 174–75 memory, 151–55 meritocracy, 189–90, 230–31 meta-rationality, 82, 115 meta-studies, 224–25 Mexico, 168, 171, 177, 242–43 microcredit, 222–23 microeconomics, 212, 225 “micro-intelligibility,” 219 mid-wage occupations, 38 military, 29, 57 Millennium Prize Problems, 207–8 minimum wage, 59, 60 modes of employment, 35–36 monetarist theory, 226 MOOCs (massive open online courses), 180 Moonwalking with Einstein (Foer), 152 Moore’s law, 10, 15–16 moral issues, 26, 130–31 morale in the workplace, 30, 36 Mormon Church, 197 Morphy, Paul, 106 motivation, 197–202, 203 movie ratings, 121 Moxon’s Master, 134 Mueller, Andreas, 59 multinational corporations, 164 Murray, Charles, 231, 249 music, 146–47, 158 Myspace, 42, 209 mysticism, 153 Nakamura, Hikaru, 80 Narrative Science, 8–9 natural gas production, 177 natural language, 7, 119, 140–41 Naum (chess program), 72 negotiations in business, 12–13, 73 Netflix, 9 Nevada, 8 The New York Times, 11–12 Newton, Isaac, 153 Ng, Jennifer Hwee Kwoon, 89 Nickel, Arno, 81 Nielsen, Dagh, 80 Nobel Prizes, 187, 216 non-tradeable sectors, 176 North American Free Trade Agreement (NAFTA), 8 Northeast US, 241 “nudge” concept, 105 Obama healthcare reform, 237–38 Occupy Wall Street, 230, 251, 253, 256 O’Daniel, Karrah, 96 offshoring, 175.

…

See also artificial intelligence (AI) Mechanical Turk, 148–49 mechanization, 126–27 media, 146 median incomes, 38, 52, 60, 253 Medicaid, 234–39, 250 medical diagnosis, 87–89, 128–29 Medicare, 232–35, 237–38, 242 Medication Adherence Scores, 124 Mediterranean Europe, 174–75 memory, 151–55 meritocracy, 189–90, 230–31 meta-rationality, 82, 115 meta-studies, 224–25 Mexico, 168, 171, 177, 242–43 microcredit, 222–23 microeconomics, 212, 225 “micro-intelligibility,” 219 mid-wage occupations, 38 military, 29, 57 Millennium Prize Problems, 207–8 minimum wage, 59, 60 modes of employment, 35–36 monetarist theory, 226 MOOCs (massive open online courses), 180 Moonwalking with Einstein (Foer), 152 Moore’s law, 10, 15–16 moral issues, 26, 130–31 morale in the workplace, 30, 36 Mormon Church, 197 Morphy, Paul, 106 motivation, 197–202, 203 movie ratings, 121 Moxon’s Master, 134 Mueller, Andreas, 59 multinational corporations, 164 Murray, Charles, 231, 249 music, 146–47, 158 Myspace, 42, 209 mysticism, 153 Nakamura, Hikaru, 80 Narrative Science, 8–9 natural gas production, 177 natural language, 7, 119, 140–41 Naum (chess program), 72 negotiations in business, 12–13, 73 Netflix, 9 Nevada, 8 The New York Times, 11–12 Newton, Isaac, 153 Ng, Jennifer Hwee Kwoon, 89 Nickel, Arno, 81 Nielsen, Dagh, 80 Nobel Prizes, 187, 216 non-tradeable sectors, 176 North American Free Trade Agreement (NAFTA), 8 Northeast US, 241 “nudge” concept, 105 Obama healthcare reform, 237–38 Occupy Wall Street, 230, 251, 253, 256 O’Daniel, Karrah, 96 offshoring, 175. See also outsourcing “off-the-grid” living, 246–47 online dating, 9, 16, 95–98, 125, 144–45 online education, 179–85 opportunity cost, 184 options-pricing theory, 203 outsourcing, 162, 163–71 overseas labor markets, 59 “P vs. NP” problem, 101 particle physics, 211–15 patent law, 17 per capita income, 170 Perelman, Grigory, 208 performance evaluation, 104 Peri, Giovanni, 162–63 “the periphery,” 175 personal service sector, 31–32 petty entrepreneurship, 61 Pew Research Center, 248–49 pharmaceutical industry, 17 Ph.D. degrees, 40 physics, 211–15, 226 Player Piano (Vonnegut), 126, 247–48 Pocket Fritz (chess program), 147–48 Poincaré conjecture, 208 poker, 49 Polanyi, Michael, 215 Polgar, Judit, 108 politics, 10–11, 227, 251–59 poor population, 121, 236, 237 popular culture, 51 population growth, 51.

Peer-to-Peer by Andy Oram

AltaVista, big-box store, c2.com, combinatorial explosion, commoditize, complexity theory, correlation coefficient, dark matter, Dennis Ritchie, fault tolerance, Free Software Foundation, Garrett Hardin, independent contractor, information retrieval, Kickstarter, Larry Wall, Marc Andreessen, moral hazard, Network effects, P = NP, P vs NP, p-value, packet switching, PalmPilot, peer-to-peer, peer-to-peer model, Ponzi scheme, power law, radical decentralization, rolodex, Ronald Coase, Search for Extraterrestrial Intelligence, semantic web, SETI@home, Silicon Valley, slashdot, statistical model, Tragedy of the Commons, UUNET, Vernor Vinge, web application, web of trust, Zimmermann PGP

It’s worth noting in passing that the previous construction is not proven to be nonparallelizable. Besides the product-of-two-primes problem, its security rests on no one knowing how to perform the repeated modular squaring in parallel. This problem is tied up with the “P vs. NC” problem in computational complexity theory and is outside the scope of this chapter. Similar to the better known “P vs. NP” problem, which concerns the question, “Which problems are easy?” the P vs. NC problem asks, “Which problems are parallelizable?”[56] Fungible micropayments All of the micropayment schemes we have previously described are nonfungible. While Alice pays Bob for resource use with some coin that represents a proof of work, he cannot redeem this token for something of value to him.

…

O’Reilly Network’s P2P directory, Remaking the Peer-to-Peer Meme OReilly, Tim, Contributors O’Reilly, Tim, Contents of this book, Remaking the Peer-to-Peer Meme–Strategic positioning and core competencies organized manual databases, Ways to fill shared databases–CDDB: A case study in how to get a manually created database organized mechanical databases, Ways to fill shared databases Ozzie, Ray, Remaking the Peer-to-Peer Meme, Immediate information sharing: The new instant messaging services, Central control and local autonomy P P in P2P is People, File sharing: Napster and successors P vs. NC problem, Nonparallelizable work functions P vs. NP problem, Nonparallelizable work functions P2P directory (O’Reilly Network), Remaking the Peer-to-Peer Meme packet delivery, best effort, The TCP rate equation: Cooperative protocols pairwise keys, Mutually-suspicious shared spaces adding new members, Inviting people into shared spaces pairwise payment model, The difficulty of distributed systems: How to exchange micropayments among peers parallel download strategy (Netscape), The TCP rate equation: Cooperative protocols parallelizable schemes, Nonparallelizable work functions partial anonymity, Partial anonymity partial hash collisions, Extended types of nonfungible micropayments minting MicroMint coins, Making money off others’ work passive-server document-anonymity, Anonymity for anonymous storage provided by Eternity Usenet, An analysis of anonymity Free Haven, An analysis of anonymity Freenet, An analysis of anonymity passwords and Publius Update operations, Update operation pathlengths characteristic (see characteristic pathlengths) query (Gnutella), Initial experiments Pavlovski, Chris, Other considerations from the case study pay-per-use web sites and PayWord, Micropayment digital cash schemes payment models in peer-to-peer systems, The difficulty of distributed systems: How to exchange micropayments among peers–The difficulty of distributed systems: How to exchange micropayments among peers payment schemes anonymous e-cash, Anonymous e-cash payment schemes CPU-based, CPU-based payment schemes PayWord, Micropayment digital cash schemes extending peer-to-peer applications, Micropayment digital cash schemes sliding scale for payment, Moderating security levels: An accountability slider payword chains (hash values), Micropayment digital cash schemes PCs as promiscuous computers, Promiscuous computers in the early days of the Internet, Peer-to-peer is as peer-to-peer does Napster leverages the power of, Where’s the content?

Reinventing Discovery: The New Era of Networked Science by Michael Nielsen

Albert Einstein, augmented reality, barriers to entry, bioinformatics, Cass Sunstein, Climategate, Climatic Research Unit, conceptual framework, dark matter, discovery of DNA, Donald Knuth, double helix, Douglas Engelbart, Douglas Engelbart, Easter island, en.wikipedia.org, Erik Brynjolfsson, fault tolerance, Fellow of the Royal Society, Firefox, Free Software Foundation, Freestyle chess, Galaxy Zoo, Higgs boson, Internet Archive, invisible hand, Jane Jacobs, Jaron Lanier, Johannes Kepler, Kevin Kelly, Large Hadron Collider, machine readable, machine translation, Magellanic Cloud, means of production, medical residency, Nicholas Carr, P = NP, P vs NP, publish or perish, Richard Feynman, Richard Stallman, selection bias, semantic web, Silicon Valley, Silicon Valley startup, Simon Singh, Skype, slashdot, social intelligence, social web, statistical model, Stephen Hawking, Stewart Brand, subscription business, tacit knowledge, Ted Nelson, the Cathedral and the Bazaar, The Death and Life of Great American Cities, The Nature of the Firm, The Wisdom of Crowds, University of East Anglia, Vannevar Bush, Vernor Vinge, Wayback Machine, Yochai Benkler

Sharing health data: Good intentions are not enough. Bulletin of the World Health Organization, 88(6), 2010. [172] Michael Polanyi. The republic of science: Its political and economic theory. Minerva, 1:54–74, 1962. http://www.missouriwestern.edu/orgs/polanyi/mp-repsc.htm. [173] Polymath participants. Deolalikar P vs NP paper. Polymath wiki, 2010-. http://michaelnielsen.org/polymath1/index.php?title=Deolalikar’s_P!%3DNP_paper. [174] Zoran Popović. CASP8 results. Foldit blog, December 17, 2008. http://fold.it/portal/node/729520. [175] Jason Priem, Dario Taraborelli, Paul Groth, and Cameron Neylon. Altmetrics: A manifesto.