Getting Started

Review: Say: In the previous lesson we explored a computationally hard problem called the Traveling Salesman Problem. The only known way to find the shortest path is to perform a brute force search, or in other words, try every possible path. There are heuristics for getting close to a good solution but no known way to get the exact solution without trying every possible path, which is prohibitively large. It would take an unreasonable amount of time to solve.

As we saw, it’s fairly easy to draw a map which will take a computer (or person) thousands of years to solve. An interesting thing about the Traveling Salesman Problem is that, even if you are the one making the map (assuming it’s not trivial), it’s also impossible for you to know the correct solution without also using the brute force approach.

Computationally hard problems are used to make encryption really strong, but we don’t totally know how this works yet. Today we’re going to look at another hard problem that moves us back toward the path to encryption. We’d like to have some way to construct a problem that is computationally hard to solve but to which we know the answer!

Activity

Distribute: Provide students with copies of Wireless Hotspot Problem - Worksheet. Students may work individually or in pairs on this challenge. You may choose to read the instructions together, to ensure that the challenge is clear and students know how to proceed.

Work on the Challenge: Students should work on the challenge for several minutes, but probably 10 at the most. You should offer help as needed, and encourage students to continue to work on their solutions. Just because students found a good solution doesn’t mean that it’s actually the best! With a more competitive class, you might want to keep a running track of the best solution found so far. Alternately, ask students to check one another’s solutions or help one another get started if they’re having trouble.

Share Results: Ask students to stop working and compare their results with classmates, other groups, or as a class. Prompts:

• What was the smallest set of hot spots they were able to find?
• What types of heuristics did you employ to find your solution? (e.g., pick the most connected corners first)
  • Use this opportunity to recall this vocabulary from the previous lesson. A heuristic is just a strategy for arriving at a “pretty good” solution when there’s no obvious way to get a perfect one.
  • Note: Even if some heuristics for this problem do a good job, none will always guarantee a perfect solution.
• Are you sure this is the actual smallest? How could you be certain?
  • Students should begin to suspect that this problem can only be solved through a brute force search, i.e., trying every combination with one node, then two, then three, and so on, until a solution is found. Clearly, this could take a very long time, just like the Traveling Salesman Problem.

Discuss: Relate the experience with this problem to that on the Traveling Salesman Problem.

Prompts:

• How is this problem similar to the Traveling Salesman Problem?
  • Possible points: it’s a graph algorithm, you’re looking for one best solution, it just seems hard to do. This question is more to draw the original connection and prepare for the following question.
• How would a computer approach this problem? How long is it going to take?
  • If students have not already noticed, confirm that this is a computationally hard problem and would require a brute force search. Just like in the Traveling Salesman Problem, the number of possible solutions is multiplied every time another node is added, so even for small graphs, this problem can take an extremely long time to solve.

Transition: The problem we just explored is actually a very famous one in computer science, technically known as the vertex cover problem. It is significant because, just like the Traveling Salesman Problem, it is computationally hard to solve perfectly. Heuristics give good solutions, but perfect solutions can only be found with a brute force search. But there is one very big difference between the Traveling Salesman Problem and the Wireless Hotspot Problem: the person who creates the problem can know the solution ahead of time - WITHOUT performing a brute force search. Let’s see how.

Distribute: Distribute to each group or student the Make Your Own Wireless Hotspot Problem - Worksheet. Students may either read through the explanation there or you can review the explanation as a class.

Following the instructions the worksheet, students have been provided space to create their own maps. Ask students to follow the steps to make a map, and keep track of their solution somewhere else (a separate sheet of paper, their journals, etc.) They should then exchange with a partner to see if they can find the results. If they follow the steps, it’s quite easy to make a problem that their classmates will have a very hard time cracking, even with just a few nodes.

Assessment

The following questions can be found on Code Studio.

1. Multiple Choice: Which of the following correctly defines a one-way function?

   a) Hard to create and hard to solve

   b) Hard to create and easy to solve

   c) Easy to create and hard to solve

   d) Easy to create and easy to solve

2. Matching: Match each word to the phrase that best describes it:

   Word/Phrase	Description
   a. Heuristic	1. Requiring many computers or a long time in order to be solved
   b. Brute force	2. Requires much more effort to solve than to create
   c. One-way function	3. Trying every possible solution
   d. Computationally hard	4. Rules or an algorithm for finding an approximate solution

3. Free Response: Given that the Traveling Salesman Problem and the Wireless Hotspot Problem are computationally hard to solve, why might the Wireless Hotspot Problem be a more ideal candidate for using an encryption method? Make reference to properties of the two problems in your answer.

Extended Learning

• Subset Sum Problem: Another one-way function that students can practice with is the subset sum problem. The problem is perhaps even easier to make than the Wireless Hotspot Problem, and has the same property of being computationally hard to solve. If you have time, this may be a good way to provide additional examples of a one-way function and further reinforce the mathematical foundations of cryptography using familiar mathematical concepts. Students can quickly make these problems for classmates and challenge them to solve them.
  • The Problem: Given a list of positive and negative numbers, is there some group of these numbers which adds up to 0?
  • Example: (45, -100, 23, 11, -14, 25, -81, 37, 10) The solution is 45, -100, 23, 11, -14, 25, 10. Don’t worry if you didn’t get it yourself; the whole point is that it’s hard to find a solution!
  • Creating the problem: Choose a set of numbers known to add up to 0 beforehand. For example, -12, -10, 3, and 19. Then add in a bunch of “distractor” values. Present a randomly sorted list containing the solution values and the distractors. There’s no guaranteed solution, other than checking all possibilities by brute force!
• Make Your Own Graphs: Students can practice cracking one-way functions with the provided map and key, or practice creating one-way functions using maps and keys of their own creation. They can use this Graph Creator tool: http://illuminations.nctm.org/Activity.aspx?id=3550

Wrap-up

Reflect: Students should complete the reflection questions at the bottom of their worksheets in preparation for the following discussion.

Discuss: Say: The Wireless Hotspot Problem is one of a category of problems called “one-way functions.” The person who creates the problem can easily know the solution, but for anyone else, finding the solution requires a brute force search. A problem you create in 20 seconds could take even the most powerful computers years to solve.

• When else have we seen things that act like one-way functions?
  • Students may make the connection to encryption. With the Vigenère cipher, if you know the key, encrypting the text is easy, but undoing it is very hard.
  • Important Note: The Vigenère cipher is actually NOT a computationally hard problem to solve. It is an attempt to make text hard to crack, but there are techniques for cracking it very quickly. The Wireless Hotspot Problem is the first one-way function we’ve actually seen that results in a computationally hard problem.
• Why might we want to use a one-way-function when designing a method of cryptography?
  • When we encrypt a piece of information, we would like it to be easy for the person doing the encryption, but hard for even a powerful computer to crack the encryption.
• In the Wireless Hotspot Problem, what could act as a “key” to our encryption?
  • Recall that the key is the portion of the encryption that remains a secret. When constructing your own map, perhaps there is some way of using those “secret nodes” as a key.
  • Note: Students don’t yet need to know HOW this will be done.