Computers have defeated the world’s greatest human chess players. Computers can sift through the huge expanse of the Internet to find you the best search result. Computers can even tell when someone is pregnant before their parents find out.

These days, it might seem like computers can tackle any sort of problem. This is not true. Furthermore, the fact that hard problems for computers exist make it possible for us to do things like shop on the Internet.

The first question to ask is how we define a hard problem for a computer. Computers are effectively limited in two areas: space and time. By space I am referring to storage space, how much memory a computer can hold. With ever-improving hardware, this is much less of an issue than it used to be. The second issue, time, is still a very serious issue. If a problem takes billions of years to solve, then we have a problem. Computers solve problems by executing algorithms, performing a series of steps to reach a goal. In computer science, we often speak of how long a problem takes to complete in terms of the size of the input to the problem. Problems that require an exponential number of steps on an input are considered to be quite hard, because they take a very very long time to solve. Here are two such problems.

The Knapsack Problem: This problem can be phrased in a number of ways. The easiest to think about it, in my opinion, is in terms of ordering dinner at a restaurant. You have a menu with a number of entrees, each with different prices and you want to order exactly $25 worth of food. The goal is to find out if this is possible and if so, what should I order?

This problem can also be phrased in terms of a knapsack that can hold 10lbs. I have a pile of items, which each weigh different amounts. How do I fill the bag with exactly 10lbs of items?

Why is this hard? Well at the moment the only known way to solve this problem is by trying every possible combination of item in the bag. Thus if you have 2 items there are 2²=4 ways to put the items in the bag. If you have 3 items there are 2³=8 ways. However if I have say 100 items, then there are 2¹⁰⁰ combinations to check. Assuming checking a combination of items takes 1 nanosecond (1 billionth of a second) then checking all combinations will take 2900 times the age of the universe. Just a little too long to reasonably handle, this is a hard problem to say the least.

Prime Factorization: Remember in middle school when you would draw factor trees? Well it turns out that all integers (non-fractions) can be written uniquely as a product of primes. How can we determine the prime factors of a number, N? Well at the moment we don’t know many ways much better than the following: If possible, divide N by 2; if not, continue to the next prime number, 3, and so on. Keep doing this up until the square root of N. Thus, for a number N we might have to check up to the square root of N different numbers to find all of its prime factors.

Now consider a huge number. One that has 200 digits (this means that the number is on the order of 10²⁰⁰). Even only checking up to the square root of that number can take a very long time (2.3*10¹⁸³ times the age of the universe).

It turns out that this is the basis of how something called public key cryptography works. Public key cryptography provides a way that anyone can encrypt some piece of data (e.g. credit card number), but only the person who came up with the encryption can then decrypt that data. Suffice it to say that this relies on the fact that its very hard to factor very large numbers. Public key cryptography is how websites such as Amazon secure your personal data so that your transactions and purchases remain secure and private.

It’s awesome that computers can solve very hard problems, but be thankful that there are still very tricky problems for computers.

By: Jonah Scheinerman

(Photo courtesy of sxc.hu)