Getting Started

Recall: Say: In a previous lesson we looked at the problem of trying to crack passwords and learned it would take a computer a very long time to try every possible combination of letters. We learned that the longer a password is, the harder it is to crack. This is because every character you add multiplies the number of possible passwords by the number of possibilities for that character. That’s pretty fast growth.

Say: Computationally Hard Problems are problems that force a computer to run through many possibilities to find the right answer. In cryptography, our desire is to have an encryption function that is easy compute if you have the key, but really hard if you don’t.

Transition: Today we’re going to look at one of the most famous problems that is thought to be computationally hard. We’ll see if we can find an algorithm to solve it, and along the way, we’ll get a better sense of what “computationally hard” really means.

Activity

Introduce the traveling salesperson problem.

Distribute the Introduction to the Traveling Salesperson Problem - Worksheet.

• Give individual students time to work on finding the shortest routes for the small examples in the worksheet.
• Make sure that students to compare their answers.
  • If two partners disagree, they should resolve it to find the shortest tour.

If you ask students how they arrived at their solutions they might say, “I tried a bunch of different paths and kept track of the shortest.” Or some form of greedy algorithm: “I want to avoid that large edge” or “I want to use that small edge.” These are good strategies, but they can always be thwarted with the question, “How do you know for sure it’s the shortest?”

Discuss.

Goal: The goal of the discussion is to bring out the fact that this would be a much harder problem for computers to solve than the shortest path problem or minimum spanning tree problem. “Hard” means that there is no known way to find the correct answer without generating ALL possible answers. Connect this problem to our desire to understand problems that are computationally hard for computers for encryption.

Prompts:

• What makes this problem harder than the shortest path problem?
  • First of all you need to make a closed path (route) of all vertices without revisiting vertices. This is a harder thing to do than just finding a path from one vertex to another. Just constructing a valid route is difficult.
  • Second, you don’t know where to start. Any edge could be part of the shortest tour. And once you pick an edge to start with, you still have no way to choose the next one. There is no way to eliminate possibilities from the start or as you go.
• What kinds of algorithms did you think about in trying to solve the problem?
  • Students might suggest strategies that leverage what they know about solving the minimum spanning tree and shortest path problems from previous lessons, such as starting with the least-cost edge in the graph, and then “greedily” connecting nodes by picking subsequent least-cost edges.
  • This is a good heuristic and might yield a tour that is better than the worst possible tour, but there is no guarantee it’s the best.
  • The only algorithm that is known to find the absolute shortest tour every time is brute force, generating every possible tour and comparing them.

Extended Learning

• If you do a quick Google search on the Traveling Salesperson Problem, you will find many many interesting resources. For example, here is a two-minute video that shows a nice visualization of some heuristics for TSP that give pretty good tours, but still not optimal, because there are just too many possibilities to consider.

Assessment

Questions:

1) Describe what it means for a problem to be “computationally hard.”

2) What strategies do people use to solve large computationally hard problems?

3) Why are computationally hard problems important in encryption strategies?

Wrap-up

Say:

If I told you that we could make an encryption scheme that was as hard to crack as it is to solve the traveling salesperson problem, would you feel reasonably assured of your security?

To answer that, let’s figure out just how hard TSP is.

Explain Exponential Growth - How many possible tours are there?

Many people for many years have tried to design an algorithm that works in all cases to find the exact optimum route for the traveling salesperson problem, with no success. So there is currently no algorithm to find the exact answer besides “brute force,” trying all the possibilities.

Since we have to calculate the distances of all the tours anyway, we might as well count how many tours there are in the first place, just so we know how many calculations we have to perform.

For this demonstration, let’s also consider a version of the problem faced by, say, an airline. For an airline, there are cities all over the world, and you can fly from any one directly to any other. So for an airline, there is a possible path that connects every possible node; we say the graph is “fully connected.”

Let’s see how the problem grows very quickly, by constructing all the possible tours for larger and larger numbers of nodes.

Let’s start with 3 nodes. There is only one possible tour. Easy.

With 4 nodes, there are only 3 possible tours. Not bad.

Here’s where it starts to get crazy. With 5 nodes there are 12 possible tours. How can you figure this out? The way shown below was to reason that a 5th node could be added between each pair of nodes for every possible 4-node tour. Here, the actual distances don’t matter because we’re just trying to count the number of tours.

Below is another view of the same thing. In this version we took each 4-node tour and “broke” one of the edges, connecting it to the new 5th node. Just a different way to think about it.

For 6 nodes we could repeat the process: add a node to every possible edge of the 12 solutions 5-node solutions. Since each of 12 solutions above has 5 edges, it means we have 12*5 = 60 tours!

Notice how fast this grows: between a graph with 3 nodes and a graph of 6 nodes, our total number of possible tours grew from 1 to 60. This problem grows very quickly!

With just 10 nodes, this grows to about 181,440 possible tours.

With just 26 nodes, this grows to a 25-digit number: 7,755,605,021,665,492,992,000,000. (By comparison, the width of the entire observable universe(!!!!) in miles is roughly a 25-digit number.)

With 100 nodes you’re up to a roughly a 155-digit number.

The math: With n nodes there are (n-1)!/2 (“n-1 factorial divided by 2”) possible tours. n! (or “n factorial”) is n(n-1)(n-2)(n-3)...(2)(1). So for example 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1. You can confirm the formula with the examples above: 5 nodes = (5-1)! / 2 = 12.

Reasonable or Unreasonable Time

Computers work fast, but they have limits. In computer science, we have an actual mathematical hard line between reasonable and unreasonable runtimes.

"Reasonable" means the number of things the computer has to do is proportional to the size of the input to the problem. For example, the Minimum Spanning Tree and Shortest Path Problems are “reasonable” because they had algorithms that solved them by considering every edge in the graph once. The amount of time it takes is proportional to the number of edges. If the number of edges is n, even if there was an algorithm that had to look at the edge n^2 times, or n^3 times, that’s still reasonable.

“Unreasonable” means the number of things the computer has to do grows as an exponent of the size of the input. So if you discovered that an algorithm made the computer do 2^n things, that’s not reasonable, because it means every time the size of the input (n) gets bigger, the solution gets massively further out of reach. n! is another running time that is considered unreasonable. In real life, “unreasonable” problems would take a modern computer trillions and trillions of years to churn through all the possibilities.

So the brute force solution to TSP is unreasonable -- at least as far as we know! In fact, it's an open question how to solve this problem efficiently. If anyone finds a solution that runs in a reasonable time, a lot of security and encryption algorithms are in trouble, because many are based on the fact that this (and related problems) are unreasonable to solve.

So now we know what “hard” is for a computer. And in the next lesson, we’ll discuss how to leverage hard problems like this one to create public keys that are tough for computers to crack.