Kermit's Korner

My life has been to seek the Absolute Truth of God; to help others find the real purpose of their lives... Attempt to make this or where ever I am; better for my having been there! Amen!

Blog Archive

  • ►  2023 (2)
    • ►  January (2)
  • ►  2022 (12)
    • ►  September (1)
    • ►  August (8)
    • ►  July (2)
    • ►  April (1)
  • ►  2021 (3)
    • ►  October (1)
    • ►  April (1)
    • ►  February (1)
  • ▼  2020 (148)
    • ►  July (2)
    • ►  June (14)
    • ►  May (17)
    • ►  April (33)
    • ▼  March (40)
      • What everybody know - yet does not understand abo...
      • Why Germany's Virus Death rate is Lower
      • Peace what where and when?
      • The Unpardonable Sin
      • The Truth most people will not read or see!
      • God's ability
      • Quand Meme means ??
      • Faith must always be part of any divine intervention
      • A spicial message on Faith and Love in action
      • Faith can perceive things that the senses cannot (...
      • Only Grace and Mercy = Salvation
      • ‘þetta reddast’
      • 'truth will set you free" phrase is being hijacked
      • Pinholes Copper pipe
      • Copper - COVID-19 pandemic
      • Getting back to normal?
      • Few have read yet many still wonder?
      • a Separated life?
      • Choosing your battle - or learning to see the rea...
      • As you begin your day so goes your day!
      • How do we get it wrong?
      • More truth - Should humans eat Meat?
      • This is not Singapore’s first epidemiological nigh...
      • Keeping Things Secret?
      • A problem with the Bible? Part 1
      • Healing Is God's Will
      • A Lifestyle Check
      • Seek me First!
      • The art of Oil pulling
      • Many lose because they do not understand
      • Languages Spoken in Each Country
      • Can your heart stand it?
      • Electric car cost?
      • Garbage Advice Why?
      • Liver + Life
      • How do people become happy?
      • How to make Milianss happy?
      • There is no such thing as a “self-made” man or woman
      • A look at the future from the past for good water
      • Narratively - A real read
    • ►  February (24)
    • ►  January (18)
  • ►  2019 (427)
    • ►  December (48)
    • ►  November (34)
    • ►  October (27)
    • ►  September (49)
    • ►  August (28)
    • ►  July (39)
    • ►  June (39)
    • ►  May (29)
    • ►  April (33)
    • ►  March (25)
    • ►  February (36)
    • ►  January (40)
  • ►  2018 (642)
    • ►  December (62)
    • ►  November (45)
    • ►  October (50)
    • ►  September (43)
    • ►  August (32)
    • ►  July (64)
    • ►  June (50)
    • ►  May (62)
    • ►  April (48)
    • ►  March (59)
    • ►  February (52)
    • ►  January (75)
  • ►  2017 (2472)
    • ►  December (100)
    • ►  November (88)
    • ►  October (186)
    • ►  September (208)
    • ►  August (349)
    • ►  July (409)
    • ►  June (397)
    • ►  May (249)
    • ►  April (113)
    • ►  March (115)
    • ►  February (147)
    • ►  January (111)
  • ►  2016 (994)
    • ►  December (99)
    • ►  November (69)
    • ►  October (98)
    • ►  September (84)
    • ►  August (83)
    • ►  July (88)
    • ►  June (67)
    • ►  May (73)
    • ►  April (71)
    • ►  March (78)
    • ►  February (111)
    • ►  January (73)
  • ►  2015 (146)
    • ►  December (15)
    • ►  November (13)
    • ►  October (17)
    • ►  September (11)
    • ►  August (23)
    • ►  July (11)
    • ►  June (14)
    • ►  May (11)
    • ►  April (8)
    • ►  March (8)
    • ►  February (10)
    • ►  January (5)
  • ►  2014 (30)
    • ►  December (11)
    • ►  November (5)
    • ►  October (2)
    • ►  September (2)
    • ►  August (3)
    • ►  July (1)
    • ►  March (2)
    • ►  February (2)
    • ►  January (2)
  • ►  2013 (2)
    • ►  November (2)
  • ►  2012 (1)
    • ►  January (1)
  • ►  2011 (16)
    • ►  December (1)
    • ►  November (1)
    • ►  October (1)
    • ►  September (2)
    • ►  August (4)
    • ►  July (2)
    • ►  May (1)
    • ►  April (1)
    • ►  February (2)
    • ►  January (1)
  • ►  2010 (8)
    • ►  November (3)
    • ►  September (1)
    • ►  July (1)
    • ►  May (1)
    • ►  April (1)
    • ►  January (1)
  • ►  2009 (11)
    • ►  October (2)
    • ►  September (1)
    • ►  July (1)
    • ►  June (2)
    • ►  May (1)
    • ►  April (1)
    • ►  March (2)
    • ►  February (1)
  • ►  2008 (9)
    • ►  November (1)
    • ►  October (2)
    • ►  September (2)
    • ►  August (1)
    • ►  June (1)
    • ►  May (1)
    • ►  February (1)
  • ►  2007 (12)
    • ►  December (1)
    • ►  November (1)
    • ►  October (1)
    • ►  July (2)
    • ►  June (1)
    • ►  May (2)
    • ►  April (2)
    • ►  February (1)
    • ►  January (1)
  • ►  2006 (7)
    • ►  October (1)
    • ►  August (1)
    • ►  July (1)
    • ►  June (2)
    • ►  May (1)
    • ►  April (1)

13 March 2020

Keeping Things Secret?


Keeping Things Secret

 Quantum computers wouldn’t be useful for browsing the internet or writing a screenplay in a coffee shop.

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 the 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.”


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. 

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, 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, a researcher at the Centrum Wiskunde & Informatica in the 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 the 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
Privacy Policy, 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.
Read more from this author | Follow @lizlandau



Why Is Washing Your Hands So Important, Anyway?






Preview thumbnail for video'Capturing a Photograph of an Atomic Bomb Blast
Capturing a Photograph of an Atomic Bomb Blast (2:54)






  Most Popular
  1. The Knapsack Problem in Computer Science Explained
  2. How the Horrific 1918 Flu Spread Across America


  3. Is China Ground Zero for a Future Pandemic?
  4. Philadelphia Threw a WWI Parade That Gave Thousands of Onlookers the Flu
  5. U.K. Storms Unearth Bones From Historic Scottish Cemetery—and Archaeologists Are Worried



  6. Ten Myths About the 1918 Flu Pandemic
  7. Spot the Difference
  8. New Exhibition Highlights Story of the Richest Man Who Ever Lived






Missing Caption
Current Issue | March 2020
March 2020 magazine cover
  • The Defiance of Florence Nightingale
  • The New Explosive Theory About What Doomed the Crew of the 'Hunley'








AL
or 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
Privacy Terms of Use
at March 13, 2020
Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

No comments:

Post a Comment

Newer Post Older Post Home
Subscribe to: Post Comments (Atom)

Featured Post

The most powerful message ever preached in past 50 years !

 AWMI.com  **  The most powerful message ever preached in past 50 years !  10 Reasons It's Better to Have the Holy Spirit ...

Popular

  • Not so fast??
    Is this the key to chronic fatigue? It's all in your head! For years, clueless mainstream docs have implied or in some cases ...
  • Who Rules The World? Part 1
      Who Rules The World? Part I [This promises to be an interesting series from Zero Hedge] Authored by Noam Chomsky, origina...

Search This Blog

Pages

  • Home

About Me

Kerminator
Have followed being self-studied and critical thinking in pursuit of the Whole Truth!
View my complete profile

Report Abuse

Labels

  • Free Energy (1)

Blog Archive

  • ►  2023 (2)
    • ►  January (2)
  • ►  2022 (12)
    • ►  September (1)
    • ►  August (8)
    • ►  July (2)
    • ►  April (1)
  • ►  2021 (3)
    • ►  October (1)
    • ►  April (1)
    • ►  February (1)
  • ▼  2020 (148)
    • ►  July (2)
    • ►  June (14)
    • ►  May (17)
    • ►  April (33)
    • ▼  March (40)
      • What everybody know - yet does not understand abo...
      • Why Germany's Virus Death rate is Lower
      • Peace what where and when?
      • The Unpardonable Sin
      • The Truth most people will not read or see!
      • God's ability
      • Quand Meme means ??
      • Faith must always be part of any divine intervention
      • A spicial message on Faith and Love in action
      • Faith can perceive things that the senses cannot (...
      • Only Grace and Mercy = Salvation
      • ‘þetta reddast’
      • 'truth will set you free" phrase is being hijacked
      • Pinholes Copper pipe
      • Copper - COVID-19 pandemic
      • Getting back to normal?
      • Few have read yet many still wonder?
      • a Separated life?
      • Choosing your battle - or learning to see the rea...
      • As you begin your day so goes your day!
      • How do we get it wrong?
      • More truth - Should humans eat Meat?
      • This is not Singapore’s first epidemiological nigh...
      • Keeping Things Secret?
      • A problem with the Bible? Part 1
      • Healing Is God's Will
      • A Lifestyle Check
      • Seek me First!
      • The art of Oil pulling
      • Many lose because they do not understand
      • Languages Spoken in Each Country
      • Can your heart stand it?
      • Electric car cost?
      • Garbage Advice Why?
      • Liver + Life
      • How do people become happy?
      • How to make Milianss happy?
      • There is no such thing as a “self-made” man or woman
      • A look at the future from the past for good water
      • Narratively - A real read
    • ►  February (24)
    • ►  January (18)
  • ►  2019 (427)
    • ►  December (48)
    • ►  November (34)
    • ►  October (27)
    • ►  September (49)
    • ►  August (28)
    • ►  July (39)
    • ►  June (39)
    • ►  May (29)
    • ►  April (33)
    • ►  March (25)
    • ►  February (36)
    • ►  January (40)
  • ►  2018 (642)
    • ►  December (62)
    • ►  November (45)
    • ►  October (50)
    • ►  September (43)
    • ►  August (32)
    • ►  July (64)
    • ►  June (50)
    • ►  May (62)
    • ►  April (48)
    • ►  March (59)
    • ►  February (52)
    • ►  January (75)
  • ►  2017 (2472)
    • ►  December (100)
    • ►  November (88)
    • ►  October (186)
    • ►  September (208)
    • ►  August (349)
    • ►  July (409)
    • ►  June (397)
    • ►  May (249)
    • ►  April (113)
    • ►  March (115)
    • ►  February (147)
    • ►  January (111)
  • ►  2016 (994)
    • ►  December (99)
    • ►  November (69)
    • ►  October (98)
    • ►  September (84)
    • ►  August (83)
    • ►  July (88)
    • ►  June (67)
    • ►  May (73)
    • ►  April (71)
    • ►  March (78)
    • ►  February (111)
    • ►  January (73)
  • ►  2015 (146)
    • ►  December (15)
    • ►  November (13)
    • ►  October (17)
    • ►  September (11)
    • ►  August (23)
    • ►  July (11)
    • ►  June (14)
    • ►  May (11)
    • ►  April (8)
    • ►  March (8)
    • ►  February (10)
    • ►  January (5)
  • ►  2014 (30)
    • ►  December (11)
    • ►  November (5)
    • ►  October (2)
    • ►  September (2)
    • ►  August (3)
    • ►  July (1)
    • ►  March (2)
    • ►  February (2)
    • ►  January (2)
  • ►  2013 (2)
    • ►  November (2)
  • ►  2012 (1)
    • ►  January (1)
  • ►  2011 (16)
    • ►  December (1)
    • ►  November (1)
    • ►  October (1)
    • ►  September (2)
    • ►  August (4)
    • ►  July (2)
    • ►  May (1)
    • ►  April (1)
    • ►  February (2)
    • ►  January (1)
  • ►  2010 (8)
    • ►  November (3)
    • ►  September (1)
    • ►  July (1)
    • ►  May (1)
    • ►  April (1)
    • ►  January (1)
  • ►  2009 (11)
    • ►  October (2)
    • ►  September (1)
    • ►  July (1)
    • ►  June (2)
    • ►  May (1)
    • ►  April (1)
    • ►  March (2)
    • ►  February (1)
  • ►  2008 (9)
    • ►  November (1)
    • ►  October (2)
    • ►  September (2)
    • ►  August (1)
    • ►  June (1)
    • ►  May (1)
    • ►  February (1)
  • ►  2007 (12)
    • ►  December (1)
    • ►  November (1)
    • ►  October (1)
    • ►  July (2)
    • ►  June (1)
    • ►  May (2)
    • ►  April (2)
    • ►  February (1)
    • ►  January (1)
  • ►  2006 (7)
    • ►  October (1)
    • ►  August (1)
    • ►  July (1)
    • ►  June (2)
    • ►  May (1)
    • ►  April (1)
Picture Window theme. Powered by Blogger.