four colour theorem

12 results back to index

pages: 236 words: 50,763

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

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

Kentucky is surrounded by Tennessee, Virginia, West Virginia, Ohio, Indiana, Illinois, and Missouri. Again, you need three colors to color Tennessee, Virginia, West Virginia, Ohio, Indiana, Illinois, and Missouri, and a fourth to color Kentucky. Figure 6-2. U.S. Map. Take any map where there is some state surrounded by a ring of an odd number of other states and that map needs four colors. Here is a map of the provinces of Armenia. Figure 6-3. Armenia. There are only two provinces that lie entirely within Armenia. Kotayk’ has six neighbors and the capital province of Yerevan has four neighbors. Every state that doesn’t border the ocean has an even number of neighbors. So the heuristic says we might be able to color this map with three colors, and we can. Figure 6-4. Armenia Colored.

Chapter 2 Nearly everything in this chapter, except the section on Occam’s razor, is a figment of my imagination meant to illustrate the unlikely world of P = NP. Chapter 3 On Milgram’s experiment, see Stanley Milgram, “The Small World Problem,” Psychology Today 2, no. 1 (1967): 60–67. The Bacon number calculation is from the Internet Movie Database. For a readable story of the four-color problem, see Robin Wilson, Four Colors Suffice: How the Map Problem Was Solved (Princeton, NJ: Princeton University Press, 2004). Chapter 4 The quotation from Cook is actually a paraphrase in modern terminology of the original quotation from his seminal paper. The original reads as follows: The theorems suggest that {tautologies} is a good candidate for an interesting set not in L*, and I feel it is worth spending considerable effort trying to prove this conjecture.

pages: 229 words: 67,599

The Logician and the Engineer: How George Boole and Claude Shannon Created the Information Age by Paul J. Nahin

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Any sufficiently advanced technology is indistinguishable from magic, Claude Shannon: information theory, conceptual framework, Edward Thorp, Fellow of the Royal Society, finite state, four colour theorem, Georg Cantor, Grace Hopper, Isaac Newton, John von Neumann, knapsack problem, New Journalism, Pierre-Simon Laplace, reversible computing, Richard Feynman, Schrödinger's Cat, Steve Jobs, Steve Wozniak, thinkpad, Thomas Bayes, Turing machine, Turing test, V2 rocket

He has described problems that would remain beyond the power of even a quantum computer to solve efficiently.16 One such problem is the following: given an arbitrary planar map, can it be colored with just three colors so that no two countries that share a common border have the same color? Since the 1976 computer-based proof that, in general, it requires four colors to color a planar map, we know that there are maps for which three colors would not be sufficient. But, nevertheless, there are particular maps for which three colors are enough. There is, alas, no efficient algorithm known that can distinguish between three-color and four-color maps, and so having a quantum computer available would be of no help. And even when a quantum algorithm is known, it may not result in a polynomial time computation. Grover’s search algorithm is such a case because, while is indeed faster than N, we know from our earlier discussion of the factoring problem that is still exponential and not polynomial. A quantum computer makes direct use of one of numerous available quantum mechanical phenomenan to manipulate information.

pages: 407 words: 116,726

Infinite Powers: How Calculus Reveals the Secrets of the Universe by Steven Strogatz

Albert Einstein, Asperger Syndrome, Astronomia nova, Bernie Sanders, clockwork universe, complexity theory, cosmological principle, Dava Sobel, double helix, Edmond Halley, Eratosthenes, four colour theorem, fudge factor, Henri Poincaré, invention of the telescope, Isaac Newton, Islamic Golden Age, Johannes Kepler, John Harrison: Longitude, Khan Academy, Laplace demon, lone genius, music of the spheres, pattern recognition, Paul Erdős, Pierre-Simon Laplace, precision agriculture, retrograde motion, Richard Feynman, Socratic dialogue, Solar eclipse in 1919, Steve Jobs, the rule of 72, the scientific method

But I think a scenario like this is not out of the question. In parts of mathematics and science, we are already experiencing the dusk of insight. There are theorems that have been proved by computers, yet no human being can understand the proof. The theorems are correct but we have no insight into why. And at this point, the machines cannot explain themselves. Consider the famous long-standing math problem called the four-color map theorem. It says that under certain reasonable constraints, any map of contiguous countries can always be colored with just four colors such that no two neighboring countries are colored the same. (Look at a typical map of Europe or Africa or any other continent besides Australia and you’ll see what I mean.) The four-color theorem was proved in 1977 with the help of a computer, but no human being could check all the steps in the argument.

See formulas Eratosthenes, 42, 49 Erdős, Paul, 294 Euclid, 32, 90–91, 188, 236 Eudoxus, method of exhaustion used by, 32 exponential functions, 127–28 exponential growth and decay, 137–39, 220–24, 251 F facial surgery, 53–56, 56 falling bodies, 66–69 Faraday, Michael, x–xi FBI fingerprinting technology, 107–13, 257 feedback loop, 138 Ferguson, Samuel, 294 Fermat, Pierre de analytic geometry, 101–3 background, 100 contributions of, 93, 120–21, 194 Descartes rivalry, 98–99 FBI fingerprinting technology, 107–13 optimization, 103–7 principle of least time, 113–18, 319n118 tangents, 118–20 xy plane, 96–97 Feynman, Richard, vii, viii–ix, 295–97 Finding Nemo (movie), 50 fingerprints database, 107–13 finite decimals, 10 fluxions, 184 foci (focal points), 81–82 force, 230–31, 252, 258 formulas circle, area of, 7, 33 force and motion, 230–31, 252, 258 functions of one variable, 124 fundamental theorem, 179–80, 211 HIV decay, 221–22 Kepler’s third law, 85 parabolic segment, 38, 39 pi, bounds of, 32 power series (area of circular segment), 190, 191 sine waves, derivative of, 258 velocity, 173 forward problem, 144–46, 175, 179–80 four-color map theorem, 293 Fourier, Jean Baptiste Joseph applications of work, 256 Fourier analysis, 267 heat flow, 249–52 string theory, 252–56 Fourier analysis, 267 Fourier series, 254 fourth dimension, 287–91 frequencies, 254, 256, 259–60 friction, 69–70, 232–33, 245 Fuller, Brock, 275 functions applications of, 125–26 exponential functions, 127–28 exponential growth and decay, 137–39 linear functions, 146–49 logarithms, 131–34 natural base (e), 134–37 nonlinear equations, 149–54 power functions, 126–27, 182 scientific notation, 128–31 three central problems of, 144–46 xy plane, 124–25 See also derivatives fundamental theorem backward problem, 180–85 constant acceleration, 172–75 differentials, 209–11 discovery of, 168–69 equation for, 179–80, 211 Leibniz’s approach to, 211–18, 213 local vs global operations, 185–86 meaning of, 179–80 motion and change, 169–72 Newton on, 182, 193–94 “paint-roller” proof, 175–79, 178 future directions, 271–94 chaos, 281–82 computers, 285–87 determinism, 277–79 dimensions, four or more, 287–91 DNA, 273–76 nonlinearity, 279–80 Poincaré’s vector fields, 282–84 predictions, 273 radar, 284–85 G Galilei, Galileo, 64–76 background, 64 constant acceleration, 173 contributions of, 59–60, 86–88 Discourses and Mathematical Demonstrations Concerning Two New Sciences, 65 falling bodies, 66–69 functions of one variable, 124 house arrest, 65–66 ideal conditions, 69–71 vs Kepler, 85–86 observations with telescope, 65 pendulums, 71–77 power functions, 126–27 principle of inertia, 231 religious beliefs, 65 Two New Sciences, 68, 70, 71–72 Galilei, Virginia (Maria Celeste), 64, 65 Gamba, Marina, 64 Gauss, Carl Friedrich, 261 geometric series, 39 geometry algebra, merge with, 93–96, 98 analytic geometry, 101–3 area of a circle, 4–8 birthplace of, 90 harmony and, 49 Kepler on, 60, 79–80, 82 in Nature, 70 Plato on, 60 Geometry (Descartes), 119 Geri’s Game (movie), 51–52, 52 Germain, Sophie, 260, 261–62 Gilbert, William, 87 Glenn, John, 237–38 global operations.

pages: 295 words: 66,824

A Mathematician Plays the Stock Market by John Allen Paulos

Benoit Mandelbrot, Black-Scholes formula, Brownian motion, business climate, business cycle, butter production in bangladesh, butterfly effect, capital asset pricing model, correlation coefficient, correlation does not imply causation, Daniel Kahneman / Amos Tversky, diversified portfolio, dogs of the Dow, Donald Trump, double entry bookkeeping, Elliott wave, endowment effect, Erdős number, Eugene Fama: efficient market hypothesis, four colour theorem, George Gilder, global village, greed is good, index fund, intangible asset, invisible hand, Isaac Newton, John Nash: game theory, Long Term Capital Management, loss aversion, Louis Bachelier, mandelbrot fractal, margin call, mental accounting, Myron Scholes, Nash equilibrium, Network effects, passive investing, Paul Erdős, Paul Samuelson, Ponzi scheme, price anchoring, Ralph Nelson Elliott, random walk, Richard Thaler, Robert Shiller, Robert Shiller, short selling, six sigma, Stephen Hawking, stocks for the long run, survivorship bias, transaction costs, ultimatum game, Vanguard fund, Yogi Berra

Given the payoffs and human psychology, the most likely outcome is for both to confess; the best outcome for the pair as a pair is for both to remain silent; the best outcome for each prisoner as an individual is to confess and have one’s partner remain silent. The charm of the dilemma has nothing to do with any interest one might have in prisoners’ rights. (In fact, it has about as much relevance to criminal justice as the four-color-map theorem has to geography.) Rather, it provides the logical skeleton for many situations we face in everyday life. Whether we’re negotiators in business, spouses in a marriage, or nations in a dispute, our choices can often be phrased in terms of the prisoner’s dilemma. If both (all) parties pursue their own interests exclusively and do not cooperate, the outcome is worse for both (all) of them; yet in any given situation, any given party is better off not cooperating.

pages: 285 words: 83,682

The Lies That Bind: Rethinking Identity by Kwame Anthony Appiah

affirmative action, assortative mating, Boris Johnson, British Empire, Donald Trump, Downton Abbey, European colonialism, Ferguson, Missouri, four colour theorem, full employment, illegal immigration, Isaac Newton, longitudinal study, luminiferous ether, Mahatma Gandhi, mass immigration, means of production, precariat, Scramble for Africa, selection bias, transatlantic slave trade, zero-sum game

That would be tempting, but the economic dimension here is anything but incidental or contingent, and not every form of status relates to class status. (The elite members of a football team have an advantage in honor, as well as in earnings, over its benchwarmers, but class isn’t the right way to describe the arrangement.) Heritability is part of the picture; so is the prospect of upward or downward mobility. The connection between class and wealth, though complex, is indissoluble. You can start to see why class became the four-color-map problem of the social sciences. The more variables we try to account for, the harder it is to solve. Indeed, given the uncertainties about precisely how class identities might be defined or demarcated, a number of sociologists have, over the decades, sought to banish the term—to abolish “class,” if not class. But, like Svevo’s character Zeno, who is constantly trying, and failing, to give up smoking, we haven’t quite bridged the vow to the deed.

pages: 245 words: 12,162

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation by William J. Cook

complexity theory, computer age, Computer Numeric Control, four colour theorem, index card, John von Neumann, linear programming, NP-complete, P = NP, p-value, RAND corporation, Richard Feynman, traveling salesman, Turing machine

We can thus color these inner regions with two colors, switching every time we cross one of the non-circuit edges. The same trick allows us to two-color the regions lying outside of the Hamiltonian circuit, yielding altogether a four-coloring of the map. In the example, the inner regions are colored dark yellow and light yellow, and the outer regions are colored dark blue and light blue. Tait knew that not all maps have Hamiltonian circuits through their borders (the map of the continental United States is a ready example), but available tricks allowed the four-color problem to be restricted to maps such that each vertex of the border graph meets exactly three edges. Furthermore, the border graph could be assumed to be three-connected, that is, it is impossible to break the graph into two parts by deleting one or Origins of the Problem two vertices.

pages: 913 words: 265,787

How the Mind Works by Steven Pinker

affirmative action, agricultural Revolution, Alfred Russel Wallace, Buckminster Fuller, cognitive dissonance, Columbine, combinatorial explosion, complexity theory, computer age, computer vision, Daniel Kahneman / Amos Tversky, delayed gratification, double helix, experimental subject, feminist movement, four colour theorem, Gordon Gekko, greed is good, hedonic treadmill, Henri Poincaré, income per capita, information retrieval, invention of agriculture, invention of the wheel, Johannes Kepler, John von Neumann, lake wobegon effect, lateral thinking, Machine translation of "The spirit is willing, but the flesh is weak." to Russian and back, Mikhail Gorbachev, Murray Gell-Mann, mutually assured destruction, Necker cube, out of africa, pattern recognition, phenotype, plutocrats, Plutocrats, random walk, Richard Feynman, Ronald Reagan, Rubik’s Cube, Saturday Night Live, scientific worldview, Search for Extraterrestrial Intelligence, sexual politics, social intelligence, Steven Pinker, theory of mind, Thorstein Veblen, Turing machine, urban decay, Yogi Berra

Something must have kept Spock from spending his days calculating pi to a quadrillion digits or memorizing the Manhattan telephone directory. Something must have impelled him to explore strange new worlds, to seek out new civilizations, and to boldly go where no man had gone before. Presumably it was intellectual curiosity, a drive to set and solve problems, and solidarity with allies—emotions all. And what would Spock have done when faced with a predator or an invading Klingon? Do a headstand? Prove the four-color map theorem? Presumably a part of his brain quickly mobilized his faculties to scope out how to flee and to take steps to avoid the vulnerable predicament in the future. That is, he had fear. Spock may not have been impulsive or demonstrative, but he must have had drives that impelled him to deploy his intellect in pursuit of certain goals rather than others. A conventional computer program is a list of instructions that the machine executes until it reaches STOP.

pages: 1,509 words: 416,377

Under the Loving Care of the Fatherly Leader: North Korea and the Kim Dynasty by Bradley K. Martin

anti-communist, Asian financial crisis, colonial rule, cuban missile crisis, Deng Xiaoping, failed state, four colour theorem, illegal immigration, informal economy, kremlinology, land reform, means of production, Mikhail Gorbachev, Potemkin village, profit motive, RAND corporation, Ronald Reagan, special economic zone, stakhanovite, UNCLOS, upwardly mobile, uranium enrichment, women in the workforce, zero-sum game

Trying to lure investors there—regardless of how the multinational negotiations might turn out—clearly was a big part of what the government had in mind when it admitted our group of visitors. Rajin and Sonbong port officials planned to expand cargo capacity from six million to 50 million tons a year in two stages—and also planned to build a brand new port in the area with annual capacity of another 50 million tons. Unlike some nearby Russian ports, they boasted, the North Korean ports didn’t freeze up in winter. A slick brochure complete with four-color maps projected that the population of 131,000 North Koreans living in the vicinity of the two ports would grow into a modern industrial city of a million people. Conceivably a purely North Korean economic zone could work, if South Korean, Japanese or other foreign interests invested in factories there. But Yasuhiro Kawashima, deputy director-general of the Bureau of Port and Airport Development of Japan’s Niigata Prefecture, cautioned that proposals to expand port facilities in Rajin, Sonbong and nearby Chongjin might go nowhere unless Pyongyang persuaded neighbors to trans-ship cargoes through the North Korean ports.

pages: 158 words: 49,168

pages: 323 words: 94,156

Chasing New Horizons: Inside the Epic First Mission to Pluto by Alan Stern, David Grinspoon

crowdsourcing, Dava Sobel, delayed gratification, four colour theorem, Kuiper Belt, Mars Rover, orbital mechanics / astrodynamics, Pluto: dwarf planet

Closely married with Alice, is the “Ralph” instrument. Its name came from a silly joke referring to the old Honeymooners’ TV show characters, Ralph and Alice Kramden. Whereas Alice’s objective was primarily to study Pluto’s atmosphere, Ralph’s objective was to map and also determine the composition of Pluto’s surface. The size of a hat box, Ralph contains two black-and-white cameras, four color filter cameras, and an “infrared mapping spectrometer” to map surface compositions. Ralph can see colors that are redder than any red humans can see, at wavelengths which are called infrared, where minerals and ices have characteristic spectral features that can be used to reveal the surface materials at any given location in Ralph’s field of view. Ralph’s spectrometer splits infrared light up into 512 spectral channels from 1.25 to 2.5 microns.

pages: 326 words: 91,559

Everything for Everyone: The Radical Tradition That Is Shaping the Next Economy by Nathan Schneider

1960s counterculture, Affordable Care Act / Obamacare, Airbnb, altcoin, Amazon Mechanical Turk, back-to-the-land, basic income, Berlin Wall, Bernie Sanders, bitcoin, blockchain, Brewster Kahle, Burning Man, Capital in the Twenty-First Century by Thomas Piketty, carbon footprint, Clayton Christensen, collaborative economy, collective bargaining, Community Supported Agriculture, corporate governance, creative destruction, crowdsourcing, cryptocurrency, Debian, disruptive innovation, do-ocracy, Donald Knuth, Donald Trump, Edward Snowden, Elon Musk, Ethereum, ethereum blockchain, Food sovereignty, four colour theorem, future of work, gig economy, Google bus, hydraulic fracturing, Internet Archive, Jeff Bezos, jimmy wales, joint-stock company, Joseph Schumpeter, Julian Assange, Kickstarter, Lyft, M-Pesa, Marc Andreessen, Mark Zuckerberg, Marshall McLuhan, mass immigration, means of production, multi-sided market, new economy, offshore financial centre, old-boy network, Peter H. Diamandis: Planetary Resources, post-work, precariat, premature optimization, pre–internet, profit motive, race to the bottom, Richard Florida, Richard Stallman, ride hailing / ride sharing, Sam Altman, Satoshi Nakamoto, self-driving car, shareholder value, sharing economy, Silicon Valley, Slavoj Žižek, smart contracts, Steve Jobs, Steve Wozniak, Stewart Brand, transaction costs, Turing test, Uber and Lyft, uber lyft, underbanked, undersea cable, universal basic income, Upton Sinclair, Vanguard fund, white flight, Whole Earth Catalog, WikiLeaks, women in the workforce, working poor, Y Combinator, Y2K, Zipcar