#[1]Smithsonian

#[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/