Slide 1MenuPS4Malthusian CatastropheMalthus’ PostulatesMalthus’ ConclusionSlide 7Malthus’ FallacySlide 9Upcoming Malthusian Catastrophes?Malthus was wrong about #2 Also“Cornocopian View”“Kay”-sian ViewInfluence of MalthusSlide 15Problem Classes if P  NP:Graph (Map) Coloring ProblemBest Map Coloring ProblemIs it ever useful to be confident that a problem is hard?Factoring ProblemBreaking Fish“Two Time” Pad“Cribs”Finding K1Reverse Engineering LorenzIntercepting TrafficBreaking TrafficChargeDavid Evanshttp://www.cs.virginia.edu/evansClass 17: Sex, Religion, and PoliticsCS150: Computer ScienceUniversity of VirginiaComputer Science2CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944Menu•Debt, Population, , •Is it useful for a problem to be hard?•How the Allies broke Fish3CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944PS4Question 1: For each f and g pair below, argue convincingly whether or not f is (1) O(g), (2) Ω(g), and (3) Θ(g) as explained above. For all questions, assume n is a non-negative integer. …(f) f: the federal debt n years from today, g: the US population n years from today (this one requires a more informal argument)4CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944Malthusian CatastropheReverend Thomas Robert Malthus, Essay on the Principle of Population, 1798“The great and unlooked for discoveries that have taken place of late years in natural philosophy, the increasing diffusion of general knowledge from the extension of the art of printing, the ardent and unshackled spirit of inquiry that prevails throughout the lettered and even unlettered world, … have all concurred to lead many able men into the opinion that we were touching on a period big with the most important changes, changes that would in some measure be decisive of the future fate of mankind.”5CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944Malthus’ Postulates“I think I may fairly make two postulata. –First, That food is necessary to the existence of man. –Secondly, That the passion between the sexes is necessary and will remain nearly in its present state. ? These two laws, ever since we have had any knowledge of mankind, appear to have been fixed laws of our nature, and, as we have not hitherto seen any alteration in them, we have no right to conclude that they will ever cease to be what they now are…”6CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944Malthus’ Conclusion“Assuming then my postulata as granted, I say, that the power of population is indefinitely greater than the power in the earth to produce subsistence for man. ? ? Population, when unchecked, increases in a geometrical ratio. Subsistence increases only in an arithmetical ratio. A slight acquaintance with numbers will show the immensity of the first power in comparison of the second.”7CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944Malthusian Catastrophe•Population growth is geometric: (kn) (k > 1)•Food supply growth is linear: (n)What does this mean as n?Food per person = food supply / population = (n) / (kn)As n approaches infinity, food per person approaches zero!8CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944Malthus’ Fallacy9CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944Malthus’ Fallacy•He forgot how he started: “The great and unlooked for discoveries that have taken place of late years in natural philosophy, the increasing diffusion of general knowledge from the extension of the art of printing, the ardent and unshackled spirit of inquiry that prevails throughout the lettered and even unlettered world…”•Agriculture is an “endless golden age” field:–Production from the same land increases as ~ (1.02n)–Increasing knowledge of farming, weather forecasting, plant domestication, genetic engineering, pest repellants, distribution channels, etc.10CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944Upcoming Malthusian Catastrophes?•Human consumption of fossil fuels grows as (kn) (fairly large k like 1.08?)•Available fuel is constant (?)http://wwwwp.mext.go.jp/hakusyo/book/hpag200001/hpag200001_2_006.html11CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944Malthus was wrong about #2 AlsoAdvances in science (birth control), medicine (higher life expectancy), education, and societal and political changes (e.g., regulation in China) have reduced k (it is < 1 in many countries now!)12CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944“Cornocopian View”•Few resources are really finite•Most things have endless golden ages•Human ingenuity and economics and politics will solve problems before they become catastrophes–No one will sell the last gallon of gas for $2.9813CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944“Kay”-sian ViewThe best way to predict the future is to invent it. — Alan Kay14CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944Influence of Malthus“In October 1838, that is, fifteen months after I had begun my systematic inquiry, I happened to read for amusement Malthus on Population, and being well prepared to appreciate the struggle for existence which everywhere goes on from long-continued observation of the habits of animals and plants, it at once struck me that under these circumstances favorable variations would tend to be preserved, and unfavorable ones to be destroyed. The results of this would be the formation of a new species. Here, then I had at last got a theory by which to work.” Charles Darwin, in his autobiography (1876)15CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944PS4Question 1: (f) f: the federal debt n years from today, g: the US population n years from today (this one requires a more informal argument) Debt increases: Spending – Revenues: this varies, but usually positives+ Interest on the existing Debt (exponential) = (kn)Population increase is not exponential: rate continues to decrease=> as n increases, debt per person approaches infinity!This will eventually be a problem, but orders of growth analysis doesn’t say when.16CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944Problem Classes if P  NP:PSorting: (n log n)Simulating Universe: O(n3)SmileysFind Best: (n)(n)NP3SATNP-CompleteNote the NP-Complete class is a ring – others are circlesCure CancerMap ColoringTraveling Salesperson17CS150 Fall 2005: Lecture 17: Saving the World, 1798-1944Graph