#[1]Smithsonian [tr?id=452270575524133&ev=PageView&noscript=1] [tr?id=784323455034815&ev=PageView&noscript=1] IFRAME: [2]https://www.googletagmanager.com/ns.html?id=GTM-M6LKQZ Accessibility Navigation [3]Primary Navigation [4]Content Toggle [5]Share [6]Search [7]SUBSCRIBE (Left) [8]RENEW (Left) [9]GIVE A GIFT (Left) [10]March 2020 magazine cover [11]Smithsonian Magazine Subscribe (Mobile) [12]Facebook [13]Instagram [14]Pinterest [15]Twitter [16]Google+ [17]Newsletter Search (BUTTON) Search Search ____________________ [18]Search [19]SmartNews [20]History [21]Science [22]Innovation [23]Arts & Culture [24]Travel [25]Did a Warrior Queen Build the Longest Maya Road? [26]Featured: Did a Warrior Queen Build the Longest Maya Road? [27]History [28]Archaeology [29]U.S. History [30]World History [31]Video [32]Newsletter [33]A Fresh Look at the Boston Massacre [34]Featured: A Fresh Look at the Boston Massacre [35]Science [36]Age of Humans [37]Future of Space Exploration [38]Human Behavior [39]Mind & Body [40]Our Planet [41]Space [42]Wildlife [43]Newsletter [44]Earth Optimism Summit [45]Why Is Washing Your Hands So Important Anyway? [46]Featured: Why Is Washing Your Hands So Important Anyway? [47]Ingenuity [48]Ingenuity Awards [49]The Innovative Spirit [50]Education [51]Energy [52]Health & Medicine [53]Technology [54]Video [55]Newsletter [56]How the Trampoline Came to Be [57]Featured: How the Trampoline Came to Be [58]Arts & Culture [59]Museum Day [60]Art [61]Books [62]Design [63]Food [64]Music & Film [65]Video [66]Newsletter [67]How the New 'Emma' Gets Austen's Irony Right [68]Featured: How the New 'Emma' Gets Austen's Irony Right [69]Travel [70]Alaska [71]American South [72]Italy [73]Paris [74]Ireland [75]Travel With Us [76]Newsletter [77]How a Remote Nevada Town Became a Basque Hotspot [78]Featured: How a Remote Nevada Town Became a Basque Hotspot [79]At the Smithsonian [80]Visit [81]Exhibitions [82]New Research [83]Artifacts [84]Curators' Corner [85]Ask Smithsonian [86]Podcasts [87]Lodging [88]Newsletter [89]Voices [90]'What Is Feminist Art?' Remakes a 1970s Exhibition [91]Featured: 'What Is Feminist Art?' Remakes a 1970s Exhibition [92]Photos [93]17th Annual Photo Contest Finalists Announced. Vote Now! [94]Photo of the Day [95]Instagram [96]Video [97]Ingenuity Awards [98]Ask Smithsonian [99]Smithsonian Channel [100]Video Contest [101]Podcasts [102]Games [103]Daily Sudoku [104]Universal Crossword [105]Daily Word Search [106]Jumble [107]Mah Jong Quest [108]KenKen [109]Backgammon [110]Subscribe (Top Menu) Current Issue [111]March 2020 magazine cover Subscribe Save 84% off the newsstand price! * [112]Subscribe (Dropdown) * [113]Renew (Dropdown) * [114]Give a Gift (Dropdown) [115]Shop [116]Smithsonian Magazine [117]Subscribe [118]SmartNews [119]History [120]Science [121]Ingenuity [122]Arts & Culture [123]Travel [124]At the Smithsonian [125]Photos [126]Video [127]Games + [128]At the Smithsonian [129]Magazine [130]Photos [131]Videos [132]Games [133]Shop Search [134]Facebook [135]Twitter [136]Age of Humans [137]Future of Space Exploration [138]Human Behavior [139]Mind & Body [140]Our Planet [141]Space [142]Wildlife [143]Newsletter [144]Earth Optimism Summit [145]Subscribe [146]Book Shop [147]Travel With Us [148]SmartNews [149]History [150]Science [151]Ingenuity [152]Arts & Culture [153]Travel [154]At the Smithsonian [155]Photos [156]Video [157]Games [158]Magazine [159]Newsletters How the Mathematical Conundrum Called the ‘Knapsack Problem’ Is All Around Us A litany of issues in business, finance, container ship loading and aircraft loading derive from this one simple dilemma yellow backpack stuffed with books The "knapsack problem" is a widespread computing challenge—and no, it doesn't have to do just with literal backpacks. (golubovy / iStock) By [160]Elizabeth Landau smithsonianmag.com March 9, 2020 Imagine you’re a thief robbing a museum exhibit of tantalizing jewelry, geodes and rare gems. You're new at this, so you only brought a single backpack. Your goal should be to get away with the most valuable objects without overloading your bag until it breaks or becomes too heavy to carry. How do you choose among the objects to maximize your loot? You could list all the artifacts and their weights to work out the answer by hand. But the more objects there are, the more taxing this calculation becomes for a person—or a computer. This fictional dilemma, the “knapsack problem,” belongs to a class of mathematical problems famous for pushing the limits of computing. And the knapsack problem is more than a thought experiment. “A lot of problems we face in life, be it business, finance, including logistics, container ship loading, aircraft loading — these are all knapsack problems,” says Carsten Murawski, professor at the University of Melbourne in Australia. “From a practical perspective, the knapsack problem is ubiquitous in everyday life.” Researchers once took advantage of the problem’s complexity to create computer security systems, but these can now be cracked since the problem has been so well studied. Today, as technology capable of shattering the locks on our digital communications loom on the horizon, the knapsack problem may inspire new ways to prepare for that revolution. All or Nothing The knapsack problem belongs to a class of “NP” problems, which stands for “nondeterministic polynomial time.” The name references how these problems force a computer to go through many steps to arrive at a solution, and the number increases dramatically based on the size of the inputs—for example, the inventory of items to choose from when stuffing a particular knapsack. By definition, NP problems also have solutions that are easy to verify (it would be trivial to check that a particular list of items does, in fact, fit in a backpack). “The problem the theoreticians started to look at was how efficiently a particular task can be carried out on a computer,” writes Keith Devlin in the book The Millennium Problems. For example: Given a list of 1 million museum artifacts with their weights and monetary values, and a backpack limited to 25 pounds, a computer would have to run through every possible combination to generate the single one with the most lucrative haul. Given an indefinite amount of time, a computer could use brute force to optimize large cases like this, but not on timescales that would be practical. “We think you could cover the entire Earth with processors and run them until the heat death of the universe and still fail to solve relatively small instances of appropriate versions of these problems,” says Noah Stephens-Davidowitz, a Microsoft Research Fellow at the Simons Institute in Berkeley, California. Some NP problems like the knapsack example have a special property: In the early 1970s, Stephen Cook and Richard Karp showed that a variety of NP problems could be converted into a single problem of formal logic. Therefore, if one could be solved and verified efficiently with an algorithm, they all could. This property is known as “NP completeness.” One of the most stubborn questions in computer science and mathematics is whether these “NP” problems, including the knapsack problem, are truly different from “P” problems, those that can be solved in what is called polynomial time. If P=NP, then it’s possible to solve every problem whose solutions are easy to verify, says Stephens-Davidowitz. So, if this inequality persists, the general knapsack problem will always be hard. IFRAME: [161]https://www.youtube.com/embed/gA0I_tFBCTE Keeping Things Secret Cryptography researchers love problems that are difficult for computers to solve because they’re useful in encrypting digital messages. Knapsack-problem-like security codes are not useful for this, as they're too easily cracked, but more complicated methods inspired by this problem are being developed, and may one day play a role in outwitting the next generation of computing. In an early knapsack-style encryption method, one person’s private key would be a list of numbers in which each is larger than the sum of its predecessors. Exchanges involving that person would use a public key that looks random but is made up of numbers from the first list with specific transformations applied. For example, if the public key is [2, 3, 4, 5], the transmitted message “1, 0, 0, 1” would be encoded as 2+0+0+5 = 7 (because 2*1=2, 3*0=0, 4*0=0, and 5*1=5). Secret numbers involved in the conversions between keys allow the original message to be unveiled. For this to work, a computer must also figure out whether any given number can be written as the sum of a subset of numbers in the private key, which becomes an easy knapsack problem. It’s akin to filling a backpack with a batch of such differently sized items — like a ring, a painting, a car and a house — and knowing you can’t stuff in anything else after you’ve checked that the ring and the painting fit. Cryptographers Ralph Merkle and Martin Hellman described this idea in 1978, but others figured out how to crack it by the early 1980s. Private information exchanges on today’s internet often use keys involving large prime numbers, and while factoring big numbers is difficult, it’s not thought to belong to the same “NP complete” class as the knapsack problem. However, computer scientists are already gearing up for a future in which quantum computers can quickly unlock these keys. Quantum computers rely on the principles of quantum mechanics, which says a particle is not located in a single position but has a probability of being in many different places unless it is pinned down and measured. While normal computers encode information in 0s and 1s, each “qubit” in a quantum computer would have a wide range of possible states related to the properties of particles. Quantum computers wouldn’t be useful for browsing the internet or writing a screenplay in a coffee shop, but they would unleash never-before-seen power on a few types of math problems. Unfortunately, those math problems make up the foundations of modern cybersecurity. “In some sense, we got really unlucky,” Stephens-Davidowitz says. “We managed to rest the security of the internet on the hardness of some of the very few problems that seem to be hard for classical computers but easy for quantum computers.” While quantum computing is in its infancy, some researchers say we’re behind in preparing for it. In 2016, the National Institute of Standards and Technology (NIST) called for new quantum-resistant encryption methods, [162]announcing 26 semi-finalists last year. One such type of algorithm being developed is called lattice-based cryptography. Instead of using numbers, it uses keys that exist in multiple dimensions and involve the formation of a lattice structure made of equally-spaced points in space. The question is where those points are, and how close a given random point is to the coordinates of a lattice. At its heart, this is a knapsack problem in more than one dimension. “My current obsession is trying to figure out how secure these lattice-based things are, ideally before we use them to run the internet,” Stephens-Davidowitz says. It remains unclear how far we really are from game-changing quantum computing. Still, many cryptography researchers see an urgent threat. Hackers could be intercepting encrypted private communications and saving the for the day quantum computers are available. “This means that we need quantum-resistant cryptography much earlier than we expect quantum computer[s] to reach their full potential,” said Leo Ducas, researcher at the Centrum Wiskunde & Informatica in the Netherlands. Routing and Rerouting Beyond cryptography research, the knapsack problem and its NP complete cousins are everywhere in real life. For example, you may have heard of the “traveling salesman” problem, which is also NP complete. The challenge here is to find the shortest route for a salesman to travel between a given number of cities before returning to the starting point. Closely related is the vehicle routing problem, which considers multiple vehicles making deliveries. Luciana Buriol, associate professor at the Universidade Federal do Rio Grande do Sul in Brazil, has attacked this problem to try to find new approaches for the health care sector. She worked with a home care service where physicians and nurses visit patients in their homes and helped optimize their routes, given a limited number of cars available for transportation. “Given 300 patients and 15 cars, you cannot find the solution in a reasonable time,” she said. “If you have days for running the algorithm you will find — but you have to find [it] in less than 2 hours, otherwise you will never use [it] in practice.” No single one-size-fits-all algorithm can solve these problems. Instead, Buriol finds quick ways to arrive at useful approximations so they can be put into action. Knapsacks All Around Us For those of us who are not computer scientists and face these kinds of problems in real life, how good are we? Murawski’s group finds preliminary results that when you give humans knapsack-like problems, we also struggle mightily. In small experiments in which participants were asked to fill a backpack on a computer screen with items carrying stated values and weights, people tended to have a harder time optimizing the backpack’s contents as the number of item options increased—the same problem computers have. The researchers say this finding may be related to “choice overload”: the way we freeze up when given too many choices, even in simple situations like buying jam at a grocery store. Yet, in the real world, we get by. Paying attention is also a knapsack problem. When driving, we face a cornucopia of possible distractions such as birds, clouds, the radio, and surrounding buildings. We must put only the most pertinent stimuli in our mental knapsacks—and generally, we do. The question remains: Given that NP complete problems are more difficult for computers than other kinds of conundrums, are they also harder for people? The limited initial results suggest they could be, which surprised Murawski. “If this turns out to be the case, it would suggest that hardness of such problems is a feature of the problems—a property of nature—and not in the eye of the beholder,” Murawski says. Like this article? SIGN UP for our newsletter ____________________ SIGN UP [163]Privacy Policy, [164]Terms of Use About Elizabeth Landau Elizabeth Landau Elizabeth Landau is a science writer and editor who splits her time between Pasadena, California, and Washington, D.C. She holds degrees from Princeton University and the Columbia University Graduate School of Journalism. [165]Read more from this author | [166]Follow @lizlandau Tags [167]Artificial Intelligence [168]Computer Science [169]Mathematics [170]Mysteries [171]Technology Previous Article Why Is Washing Your Hands So Important, Anyway? Next Article Humans Have Been Taking Out Insurance Policies for at Least 30,000 Years We Recommend [172]A Leopard’s Carefully Planned Ambush Is Ruined By A Hyena (3:51) A female leopard uses her superior night vision to get closer to a herd of grazing impala. Just as she’s about to pounce, a hyena shows up revealing her position and taking away her element of surprise. Preview thumbnail for video'Bouncing Baboons Navigate Tall Grass A troop of Kinda baboons traverse across grassy plains to get to a nearby woodland. Because the grass is too high for them to see over, they rely on a curious strategy: bouncing instead of running Bouncing Baboons Navigate Tall Grass (2:20) Preview thumbnail for video'A Coconut Octopus Uses Tools to Snatch a Crab Coconut octopuses are among the most intelligent invertebrates around: They use tools, carry their shelters around for when they need them, and, fittingly, adopt an underwater walking motion that's very similar to humans. A Coconut Octopus Uses Tools to Snatch a Crab (2:34) Preview thumbnail for video'How Wallis Simpson Infiltrated British Royalty There aren't many rumors that American socialite Wallis Simpson hasn't been subjected to. So here's how she actually infiltrated the British monarchy. How Wallis Simpson Infiltrated British Royalty (4:18) Preview thumbnail for video'How to Achieve Flawless Beauty The bust of Nefertiti contains one of the most beautiful faces in the world. So beautiful, a mathematical formula was used to sculpt it. How to Achieve Flawless Beauty (2:54) Comment on this Story Please enable JavaScript to view the [173]comments powered by Disqus. [174]comments powered by Disqus Photo of the day [175]Two girls run up the rounded walls of the Heydar Aliyev Center in the heart of Baku. Two girls at the Heydar Aliyev Center Photo of the Day» Most Popular 1. [176]The Knapsack Problem in Computer Science Explained 2. [177]Philadelphia Threw a WWI Parade That Gave Thousands of Onlookers the Flu 3. [178]WWII Bunker Used by Churchill's 'Secret Army' Unearthed in Scotland 4. [179]How the Horrific 1918 Flu Spread Across America 5. [180]Six Castles You Can Visit in the United States 6. [181]John Singer Sargent 'Abhorred' Making His Lavish Portraits, So He Took Up Charcoal to Get the Job Done 7. [182]Walls Made of Ancient Human Leg Bones Found Beneath Belgian Church 8. [183]Once Attributed to a Male Artist, 'David and Goliath' Painting Identified as the Work of Artemisia Gentileschi 9. [184]Is China Ground Zero for a Future Pandemic? 10. [185]Spot the Difference 11. [186]Ten Myths About the 1918 Flu Pandemic 12. [187]What Happened When Hong Kong's Schools Went Virtual to Combat the Spread of Coronavirus 13. [188]Father and Four-Year-Old Son Find Ancient Human Remains While Biking in Washington State 14. [189]For 40 Years, This Russian Family Was Cut Off From All Human Contact, Unaware of World War II 15. [190]A Guide to What to Know About COVID-19 [191]Circulation Subscribe [192]“Machu Featured Videos [193]Missing Caption [194]An Astrophysicist Talks Understanding Our Place in the Universe [195]Missing Caption [196]This Molecule Could Explain the Origin of Life Current Issue | March 2020 [197]March 2020 magazine cover * [198]The Defiance of Florence Nightingale * [199]The New Explosive Theory About What Doomed the Crew of the 'Hunley' * [200]Why Wolverines Are the Arctic Animal We Love to Hate [201]View Table of Contents Subscribe Save 84% off the newsstand price! First & Last Name Last Name ____________________ First Name ____________________ Address 1 ____________________ Address 2 ____________________ City / State City ____________________ State [AL] Zip ____________________ Email Address Enter your email address ____________________ (BUTTON) Continue or [202]Give a Gift Newsletters Get the best of Smithsonian magazine by email. Keep up-to-date on: * History * Science & Innovation * Art * Travel * Special Offers Sign-Up Now Email Address Enter your email address ____________________ [203]Privacy [204]Terms of Use (BUTTON) Sign up [205]Smithsonian Magazine [206]SmartNews [207]History [208]Science [209]Ingenuity [210]Arts & Culture [211]Travel [212]At the Smithsonian [213]Photos [214]Video [215]Games [216]About [217]Contact [218]Advertising [219]Sustainability [220]Subscribe [221]RSS [222]Member Services [223]Smithsonian Institution [224]Air & Space Magazine [225]Smithsonian Store [226]Smithsonian Journeys [227]Smithsonian Channel [228]Smithsonian Books © Copyright 2020 Smithsonian Magazine. [229]Privacy Statement [230]Cookie Policy [231]Terms of Use [232]Advertising Notice [233]Smithsonian Institution dcsimg References Visible links 1. https://static-media.smithsonianmag.com/xml/opensearch/smith_opensearch.xml 2. https://www.googletagmanager.com/ns.html?id=GTM-M6LKQZ 3. https://www.smithsonianmag.com/science-nature/why-knapsack-problem-all-around-us-180974333/#Primary-Navigation 4. https://www.smithsonianmag.com/science-nature/why-knapsack-problem-all-around-us-180974333/#Page-Content 5. https://www.smithsonianmag.com/science-nature/why-knapsack-problem-all-around-us-180974333/#share 6. https://www.smithsonianmag.com/search 7. https://subscribe.smithsonianmag.com/sub.php?idx=245&inetz=header-L-D&ipromo=|perm|sub||header||blue||DFLT 8. https://smt.pcdfusion.com/pcd/Order?pId=13910 9. https://subscribe.smithsonianmag.com/gift.php?idx=246&inetz=header-L-D&ipromo=|perm|gift||header||blue||DFLT 10. https://subscribe.smithsonianmag.com/sub.php?idx=245&inetz=header-2&ipromo=|perm|sub||header|m|cover|80x105|auto-default 11. https://www.smithsonianmag.com/ 12. https://www.facebook.com/smithsonianmagazine 13. http://instagram.com/smithsonianmagazine 14. http://www.pinterest.com/smithsonianmag/ 15. https://twitter.com/SmithsonianMag 16. https://plus.google.com/116602523162239426012?prsrc=3 17. https://www.smithsonianmag.com/newsletters/subscribe/ 18. https://www.smithsonianmag.com/search/?q= 19. https://www.smithsonianmag.com/smart-news/ 20. https://www.smithsonianmag.com/smartnews/history-archaeology/ 21. https://www.smithsonianmag.com/smartnews/science/ 22. https://www.smithsonianmag.com/smartnews/ideas-innovations/ 23. https://www.smithsonianmag.com/smartnews/arts-culture/ 24. https://www.smithsonianmag.com/smartnews/travel/ 25. https://www.smithsonianmag.com/smart-news/warrior-queens-white-road-yucatan-may-have-connected-cities-and-villages-180974358/ 26. https://www.smithsonianmag.com/smart-news/warrior-queens-white-road-yucatan-may-have-connected-cities-and-villages-180974358/ 27. https://www.smithsonianmag.com/history/ 28. https://www.smithsonianmag.com/history/archaeology/ 29. https://www.smithsonianmag.com/history/us-history/ 30. https://www.smithsonianmag.com/history/world-history/ 31. https://www.smithsonianmag.com/videos/category/history/ 32. https://www.smithsonianmag.com/history/newsletter-history/ 33. https://www.smithsonianmag.com/history/fresh-look-boston-massacre-250-years-after-event-jumpstarted-revolution-180974342/ 34. https://www.smithsonianmag.com/history/fresh-look-boston-massacre-250-years-after-event-jumpstarted-revolution-180974342/ 35. https://www.smithsonianmag.com/science-nature/ 36. https://www.smithsonianmag.com/science-nature/age-humans/ 37. https://www.smithsonianmag.com/science-nature/future-space-exploration/ 38. https://www.smithsonianmag.com/science-nature/human-behavior/ 39. https://www.smithsonianmag.com/science-nature/mind-body/ 40. https://www.smithsonianmag.com/science-nature/our-planet/ 41. https://www.smithsonianmag.com/science-nature/space/ 42. https://www.smithsonianmag.com/science-nature/wildlife/ 43. https://www.smithsonianmag.com/science-nature/newsletter-science/ 44. https://www.smithsonianmag.com/science-nature/earth-optimism-summit/ 45. https://www.smithsonianmag.com/science-nature/why-washing-your-hands-so-important-anyway-180974355/ 46. https://www.smithsonianmag.com/science-nature/why-washing-your-hands-so-important-anyway-180974355/ 47. https://www.smithsonianmag.com/innovation/ 48. https://www.smithsonianmag.com/innovation/ingenuity-awards/ 49. https://www.smithsonianmag.com/innovation/innovative-spirit/ 50. https://www.smithsonianmag.com/innovation/education/ 51. https://www.smithsonianmag.com/innovation/energy/ 52. https://www.smithsonianmag.com/innovation/health-medicine/ 53. https://www.smithsonianmag.com/innovation/technology/ 54. https://www.smithsonianmag.com/videos/category/innovation/ 55. https://www.smithsonianmag.com/innovation/newsletter-innovation/ 56. https://www.smithsonianmag.com/innovation/how-trampoline-came-be-180974343/ 57. https://www.smithsonianmag.com/innovation/how-trampoline-came-be-180974343/ 58. https://www.smithsonianmag.com/arts-culture/ 59. https://www.smithsonianmag.com/arts-culture/museum-day/ 60. https://www.smithsonianmag.com/arts-culture/art/ 61. https://www.smithsonianmag.com/arts-culture/books/ 62. https://www.smithsonianmag.com/arts-culture/design/ 63. https://www.smithsonianmag.com/arts-culture/food/ 64. https://www.smithsonianmag.com/arts-culture/music-film/ 65. https://www.smithsonianmag.com/videos/category/arts-culture/ 66. https://www.smithsonianmag.com/arts-culture/newsletter-arts-culture/ 67. https://www.smithsonianmag.com/arts-culture/what-autumn-de-wildes-emma-gets-right-about-jane-austens-irony-180974344/ 68. https://www.smithsonianmag.com/arts-culture/what-autumn-de-wildes-emma-gets-right-about-jane-austens-irony-180974344/ 69. https://www.smithsonianmag.com/travel/ 70. https://www.smithsonianmag.com/travel/alaska/ 71. https://www.smithsonianmag.com/travel/american-south/ 72. https://www.smithsonianmag.com/travel/italy/ 73. https://www.smithsonianmag.com/travel/paris/ 74. https://www.smithsonianmag.com/travel/ireland/ 75. https://www.smithsonianmag.com/journeys/ 76. https://www.smithsonianmag.com/travel/newsletter-travel/ 77. https://www.smithsonianmag.com/travel/how-remote-nevada-town-became-bastion-basque-culture-180974274/ 78. https://www.smithsonianmag.com/travel/how-remote-nevada-town-became-bastion-basque-culture-180974274/ 79. https://www.smithsonianmag.com/smithsonian-institution/ 80. https://www.smithsonianmag.com/smithsonian-institution/plan-your-visit-smithsonian/ 81. https://www.smithsonianmag.com/smithsonian-institution/events-exhibitions/ 82. https://www.smithsonianmag.com/smithsonian-institution/new-research/ 83. https://www.smithsonianmag.com/smithsonian-institution/objects-collection/ 84. https://www.smithsonianmag.com/smithsonian-institution/curators-corner/ 85. https://www.smithsonianmag.com/smithsonian-institution/ask-smithsonian/ 86. https://www.smithsonianmag.com/smithsonian-institution/podcasts/ 87. https://www.smithsonianmag.com/smithsonian-institution/lodging/ 88. https://www.smithsonianmag.com/smithsonian-institution/newsletter-smithsonian-institution/ 89. https://www.smithsonianmag.com/smithsonian-institution/ats-voices/ 90. https://www.smithsonianmag.com/smithsonian-institution/more-forty-years-later-artists-answer-still-relevant-question-what-feminist-art-180974350/ 91. https://www.smithsonianmag.com/smithsonian-institution/more-forty-years-later-artists-answer-still-relevant-question-what-feminist-art-180974350/ 92. https://www.smithsonianmag.com/photos/ 93. https://www.smithsonianmag.com/photos/17th-annual-photo-contest-finalists/ 94. https://www.smithsonianmag.com/photocontest/photo-of-the-day/ 95. https://www.smithsonianmag.com/instagram/ 96. https://www.smithsonianmag.com/videos/ 97. https://www.smithsonianmag.com/videos/category/smithsonian-ingenuity-awards/ 98. https://www.smithsonianmag.com/videos/category/ask-smithsonian/ 99. https://www.smithsonianmag.com/videos/category/smithsonian-channel/ 100. https://www.smithsonianmag.com/videos/contest/ 101. https://www.smithsonianmag.com/videos/podcasts/ 102. https://www.smithsonianmag.com/games/ 103. https://www.smithsonianmag.com/games/daily-sudoku-180940712/ 104. https://www.smithsonianmag.com/games/universal-crossword-puzzle-180940711/ 105. https://www.smithsonianmag.com/games/daily-word-search-180958328/ 106. https://www.smithsonianmag.com/games/jumble-180958308/ 107. https://www.smithsonianmag.com/games/mah-jong-quest-180958325/ 108. https://www.smithsonianmag.com/games/ken-ken-180958307/ 109. https://www.smithsonianmag.com/games/backgammon-180958344/ 110. https://subscribe.smithsonianmag.com/sub.php?idx=245&inetz=top-nav-R-D&ipromo=|perm|sub||text||red||DFLT 111. https://subscribe.smithsonianmag.com/sub.php?idx=245&inetz=dropdown-cover-R-D&ipromo=|perm|sub||dropdown||cover||DFLT 112. https://subscribe.smithsonianmag.com/sub.php?idx=245&inetz=dropdown-R-D&ipromo=|perm|sub||dropdown||||DFLT 113. https://smt.pcdfusion.com/pcd/Order?pId=13910 114. https://subscribe.smithsonianmag.com/gift.php?idx=246&inetz=dropdown-R-D&ipromo=|perm|gift||dropdown||||DFLT 115. https://www.smithsonianstore.com/home.do?code=H1IBSMAD&utm_source=Smithsonianmag.com&utm_medium=shoplink&utm_campaign=hol2016 116. https://www.smithsonianmag.com/ 117. https://subscribe.smithsonianmag.com/sub.php?idx=245&inetz=sticky-top-nav-D&ipromo=|perm|sub||text||red||DFLT 118. https://www.smithsonianmag.com/smart-news/ 119. https://www.smithsonianmag.com/history/ 120. https://www.smithsonianmag.com/science-nature/ 121. https://www.smithsonianmag.com/innovation/ 122. https://www.smithsonianmag.com/arts-culture/ 123. https://www.smithsonianmag.com/travel/ 124. https://www.smithsonianmag.com/smithsonian-institution/ 125. https://www.smithsonianmag.com/photos/ 126. https://www.smithsonianmag.com/videos/ 127. https://www.smithsonianmag.com/games/ 128. https://www.smithsonianmag.com/smithsonian-institution/ 129. https://www.smithsonianmag.com/issue/march-2020/ 130. https://www.smithsonianmag.com/photos/ 131. https://www.smithsonianmag.com/videos/ 132. https://www.smithsonianmag.com/games/ 133. https://www.smithsonianstore.com/home.do?code=H1IBSMAD&utm_source=Smithsonianmag.com&utm_medium=shoplink&utm_campaign=hol2016 134. https://www.facebook.com/smithsonianmagazine 135. https://twitter.com/SmithsonianMag 136. https://www.smithsonianmag.com/science-nature/age-humans/ 137. https://www.smithsonianmag.com/science-nature/future-space-exploration/ 138. https://www.smithsonianmag.com/science-nature/human-behavior/ 139. https://www.smithsonianmag.com/science-nature/mind-body/ 140. https://www.smithsonianmag.com/science-nature/our-planet/ 141. https://www.smithsonianmag.com/science-nature/space/ 142. https://www.smithsonianmag.com/science-nature/wildlife/ 143. https://www.smithsonianmag.com/science-nature/newsletter-science/ 144. https://www.smithsonianmag.com/science-nature/earth-optimism-summit/ 145. https://subscribe.smithsonianmag.com/sub.php?idx=245&inetz=mobile-menu-subscribe&ipromo=|perm|sub||mobile-menu||red||auto-default 146. https://www.smithsonianbooks.com/ 147. http://www.smithsonianjourneys.org/ 148. https://www.smithsonianmag.com/smart-news/ 149. https://www.smithsonianmag.com/history/ 150. https://www.smithsonianmag.com/science-nature/ 151. https://www.smithsonianmag.com/innovation/ 152. https://www.smithsonianmag.com/arts-culture/ 153. https://www.smithsonianmag.com/travel/ 154. https://www.smithsonianmag.com/smithsonian-institution/ 155. https://www.smithsonianmag.com/photos/ 156. https://www.smithsonianmag.com/videos/ 157. https://www.smithsonianmag.com/games/ 158. https://www.smithsonianmag.com/issue/march-2020/ 159. https://www.smithsonianmag.com/newsletters/subscribe/ 160. https://www.smithsonianmag.com/author/elizabeth-landau/ 161. https://www.youtube.com/embed/gA0I_tFBCTE 162. https://www.nist.gov/news-events/news/2019/01/nist-reveals-26-algorithms-advancing-post-quantum-crypto-semifinals 163. https://www.smithsonianmag.com/science-nature/why-knapsack-problem-all-around-us-180974333/ 164. https://www.smithsonianmag.com/science-nature/why-knapsack-problem-all-around-us-180974333/ 165. https://www.smithsonianmag.com/author/elizabeth-landau/ 166. https://twitter.com/lizlandau 167. https://www.smithsonianmag.com/tag/artificial-intelligence/ 168. https://www.smithsonianmag.com/tag/computer-science-1/ 169. https://www.smithsonianmag.com/tag/mathematics/ 170. https://www.smithsonianmag.com/tag/mysteries/ 171. https://www.smithsonianmag.com/tag/technology/ 172. https://www.smithsonianmag.com/videos/category/science/a-leopards-carefully-planned-ambush-is-ruin/ 173. http://disqus.com/?ref_noscript 174. http://disqus.com/ 175. https://www.smithsonianmag.com/photocontest/photo-of-the-day/2020-03-11/two-girls-at-the-heydar-aliyev-center/ 176. https://www.smithsonianmag.com/science-nature/why-knapsack-problem-all-around-us-180974333/ 177. https://www.smithsonianmag.com/history/philadelphia-threw-wwi-parade-gave-thousands-onlookers-flu-180970372/ 178. https://www.smithsonianmag.com/smart-news/wwii-bunker-churchills-secret-army-discovered-scotland-180974389/ 179. https://www.smithsonianmag.com/history/journal-plague-year-180965222/ 180. https://www.smithsonianmag.com/travel/six-castles-you-can-visit-united-states-180974323/ 181. https://www.smithsonianmag.com/smithsonian-institution/john-singer-sargent-abhorred-making-his-lavish-portraits-so-he-took-charcoal-get-job-done-180974360/ 182. https://www.smithsonianmag.com/smart-news/walls-made-ancient-human-leg-bones-unearthed-beneath-church-belgium-180974255/ 183. https://www.smithsonianmag.com/smart-news/painting-david-and-goliath-once-attributed-male-artist-revealed-work-artemisia-gentileschi-180974312/ 184. https://www.smithsonianmag.com/science-nature/china-ground-zero-future-pandemic-180965213/ 185. https://www.smithsonianmag.com/games/spot-difference-180968040/ 186. https://www.smithsonianmag.com/history/ten-myths-about-1918-flu-pandemic-180967810/ 187. https://www.smithsonianmag.com/innovation/what-can-americans-learn-from-hong-kongs-unplanned-experiment-online-learning-during-coronavirus-180974331/ 188. https://www.smithsonianmag.com/smart-news/erosion-keeps-revealing-ancient-human-remains-washington-state-trail-180974120/ 189. https://www.smithsonianmag.com/history/for-40-years-this-russian-family-was-cut-off-from-all-human-contact-unaware-of-world-war-ii-7354256/ 190. https://www.smithsonianmag.com/smart-news/everything-you-need-know-about-covid-19-180974313/ 191. https://subscribe.smithsonianmag.com/sub.php?idx=245&inetz=www-page-right-rail-CL&ipromo=|rmnt|sub||banner||3-covers|300x200|CTRL 192. https://www.smithsonianjourneys.org/tours/machu-picchu-galapagos/itinerary/?src=sjmod-new-s&utm_source=smithsonianmag.com&utm_medium=module&utm_campaign=sjmod-new-s&utm_content=Machu Picchu and the Galapagos 193. https://www.smithsonianmag.com/videos/category/innovation/astrophysicist-michelle-thaller-on-understan/ 194. https://www.smithsonianmag.com/videos/category/innovation/astrophysicist-michelle-thaller-on-understan/ 195. https://www.smithsonianmag.com/videos/category/science/this-molecule-could-explain-the-origin-of-life/ 196. https://www.smithsonianmag.com/videos/category/science/this-molecule-could-explain-the-origin-of-life/ 197. https://www.smithsonianmag.com/issue/march-2020/ 198. https://www.smithsonianmag.com/history/the-worlds-most-famous-nurse-florence-nightingale-180974155/ 199. https://www.smithsonianmag.com/history/new-explosive-theory-what-doomed-crew-hunley-180974159/ 200. https://www.smithsonianmag.com/science-nature/wolverines-arctic-animal-love-hate-180974160/ 201. https://www.smithsonianmag.com/issue/march-2020/ 202. https://subscribe.smithsonianmag.com/gift.php?idx=246&inetz=www-page-subscription-form&ipromo=|perm|gift||banner|m|embedded-form|338x440| 203. https://www.smithsonianmag.com/about/privacy/ 204. https://www.si.edu/termsofuse 205. https://www.smithsonianmag.com/ 206. https://www.smithsonianmag.com/smart-news/ 207. https://www.smithsonianmag.com/history/ 208. https://www.smithsonianmag.com/science-nature/ 209. https://www.smithsonianmag.com/innovation/ 210. https://www.smithsonianmag.com/arts-culture/ 211. https://www.smithsonianmag.com/travel/ 212. https://www.smithsonianmag.com/smithsonian-institution/ 213. https://www.smithsonianmag.com/photos/ 214. https://www.smithsonianmag.com/videos/ 215. https://www.smithsonianmag.com/games/ 216. https://www.smithsonianmag.com/about/ 217. https://www.smithsonianmag.com/contact/ 218. https://www.smithsonianmag.com/advertising/ 219. https://www.smithsonianmag.com/sustainability/ 220. https://subscribe.smithsonianmag.com/sub.php?idx=245&inetz=www-page-footer&ipromo=|perm|sub||text||grey||DFLT 221. https://www.smithsonianmag.com/rss/ 222. https://www.smithsonianmag.com/member-services/ 223. https://www.si.edu/ 224. https://www.airspacemag.com/ 225. https://www.smithsonianstore.com/home.do?code=H1IBSMAD&utm_source=Smithsonianmag.com&utm_medium=globalfooter&utm_campaign=referlink 226. https://www.smithsonianjourneys.org/catalog/?src=sjmod-new-hp&utm_source=smithsonianmag.com&utm_medium=module&utm_campaign=sjmod-new-hp&utm_content=footer 227. https://www.smithsonianchannel.com/ 228. https://www.smithsonianbooks.com/ 229. https://www.smithsonianmag.com/about/privacy/ 230. https://www.smithsonianmag.com/about/cookie-policy/ 231. https://www.si.edu/termsofuse 232. https://www.smithsonianmag.com/privacy/ad-choices/ 233. https://www.si.edu/ Hidden links: 235. https://subscribe.smithsonianmag.com/sub.php?idx=245&inetz=mobile-header&ipromo=|perm|sub||mobile-header||red|button|auto-default 236. https://www.smithsonianmag.com/search/?q= 237. https://www.smithsonianmag.com/science-nature/why-washing-your-hands-so-important-anyway-180974355/ 238. https://www.smithsonianmag.com/science-nature/ostrich-beads-lesotho-social-networks-180974368/ 239. https://www.smithsonianmag.com/videos/category/science/bouncing-baboons-navigate-tall-grass/ 240. https://www.smithsonianmag.com/videos/category/science/a-coconut-octopus-uses-tools-to-snatch-a-crab/ 241. https://www.smithsonianmag.com/videos/category/history/wallis-simpson-a-polished-arrow/ 242. https://www.smithsonianmag.com/videos/category/history/how-to-achieve-flawless-beauty/