Read Online 100 Essential Things You Didn't Know You Didn't Know by John D. Barrow - Free Book Online Page B
Authors: John D. Barrow
Ads: Link
double the size of our sheet of A4 paper, going to A3, to A2 and so on? After just 90 doublings we have passed all the stars and the visible galaxies, and reached the edge of the entire visible Universe, 14 billion light years away. There are no doubt lots more universe farther away than this, but this is the greatest distance from which light has had time to reach us since the expansion of the Universe began 14 billion years ago. It is our cosmic horizon.
Drawing together the large and the small, we have discovered that just 204 halvings and doublings of a piece of paper take us from the smallest to the largest dimensions of physical reality, from the quantum origins of space to the edge of the visible Universe.
27
Easy and Hard Problems
Finding a hard instance of this famously hard problem can be a hard problem.
Brian Hayes
It takes a long while to complete a large jigsaw puzzle, but just an instant to check that the puzzle is solved. It takes a fraction of a second for your computer to multiply two large numbers together, but it would take you (and your computer) a long time to find the two factors that have been multiplied together to make a big number. It has long been suspected, but never proved or disproved (and there is a one-million-dollar prize for doing either), that there is a real division between ‘hard’ and ‘easy’ problems that reflects the amount of calculating time that needs to be used to solve them.
Most of the calculations, or information-gathering tasks, that we have to do by hand, like completing our tax returns, have the feature that the amount of calculating to be done grows in proportion to the number of pieces we have to handle. If we have three sources of income we have to do three times as much work. Similarly, on our computer it takes ten times longer to download a file that is ten times bigger. Ten books will generally take ten times as long to read as one. This pattern is characteristic of ‘easy’ problems. They may not be easy in the usual sense, but when you add lots of them together the amount of work required doesn’t grow very quickly. Computers can easily cope with these problems.
Unfortunately, we often encounter another type of problem that is far less easy to control. Each time we add an extra piece to the calculation, we find that the calculation time required to solve it
doubles
. Very soon the total time required becomes stupendously large, and even the fastest computers on Earth can be easily defeated. These are what we mean by ‘hard’ problems. 5
Surprisingly, ‘hard’ problems are not necessarily horribly complicated or mind-bogglingly difficult. They just involve a lot of possibilities. Multiplying together two large prime numbers is a computationally ‘easy’ task. You can do it in your head, with pencil and paper or on a calculator, as you wish. But if you give the answer to someone else and ask them to find the two prime numbers that were used in the multiplication, then they might be facing a lifetime of searching with the world’s fastest computers.
If you want to try one of these ‘hard’ problems for yourself, one that sounds deceptively easy, then find the two prime numbers that add up to give 389965026819938. fn1
These ‘trapdoor’ operations – so called because, like falling through a trapdoor, it is so much easier to go in one direction than in the reverse – are not altogether bad things. They make life difficult for us but they also make life difficult for people whose lives we are trying to make difficult for a very good reason. All the world’s principal security codes exploit trapdoor operations. Every time you shop online or extract cash from an ATM machine you are using them. Your pin number is combined with large prime numbers in such a way that any hacker or computer criminal wanting to steal your account details would have to factor a very large number into the two big prime numbers that were multiplied together to get at
Drawing together the large and the small, we have discovered that just 204 halvings and doublings of a piece of paper take us from the smallest to the largest dimensions of physical reality, from the quantum origins of space to the edge of the visible Universe.
27
Easy and Hard Problems
Finding a hard instance of this famously hard problem can be a hard problem.
Brian Hayes
It takes a long while to complete a large jigsaw puzzle, but just an instant to check that the puzzle is solved. It takes a fraction of a second for your computer to multiply two large numbers together, but it would take you (and your computer) a long time to find the two factors that have been multiplied together to make a big number. It has long been suspected, but never proved or disproved (and there is a one-million-dollar prize for doing either), that there is a real division between ‘hard’ and ‘easy’ problems that reflects the amount of calculating time that needs to be used to solve them.
Most of the calculations, or information-gathering tasks, that we have to do by hand, like completing our tax returns, have the feature that the amount of calculating to be done grows in proportion to the number of pieces we have to handle. If we have three sources of income we have to do three times as much work. Similarly, on our computer it takes ten times longer to download a file that is ten times bigger. Ten books will generally take ten times as long to read as one. This pattern is characteristic of ‘easy’ problems. They may not be easy in the usual sense, but when you add lots of them together the amount of work required doesn’t grow very quickly. Computers can easily cope with these problems.
Unfortunately, we often encounter another type of problem that is far less easy to control. Each time we add an extra piece to the calculation, we find that the calculation time required to solve it
doubles
. Very soon the total time required becomes stupendously large, and even the fastest computers on Earth can be easily defeated. These are what we mean by ‘hard’ problems. 5
Surprisingly, ‘hard’ problems are not necessarily horribly complicated or mind-bogglingly difficult. They just involve a lot of possibilities. Multiplying together two large prime numbers is a computationally ‘easy’ task. You can do it in your head, with pencil and paper or on a calculator, as you wish. But if you give the answer to someone else and ask them to find the two prime numbers that were used in the multiplication, then they might be facing a lifetime of searching with the world’s fastest computers.
If you want to try one of these ‘hard’ problems for yourself, one that sounds deceptively easy, then find the two prime numbers that add up to give 389965026819938. fn1
These ‘trapdoor’ operations – so called because, like falling through a trapdoor, it is so much easier to go in one direction than in the reverse – are not altogether bad things. They make life difficult for us but they also make life difficult for people whose lives we are trying to make difficult for a very good reason. All the world’s principal security codes exploit trapdoor operations. Every time you shop online or extract cash from an ATM machine you are using them. Your pin number is combined with large prime numbers in such a way that any hacker or computer criminal wanting to steal your account details would have to factor a very large number into the two big prime numbers that were multiplied together to get at
Similar Books
