RSA Laboratories

2.3.12 What are some other hard problems?

There are many other kinds of hard problems. The list of NP-complete problems (see Question 2.3.1) is extensive and growing. So far, none of these has been effectively applied towards producing a public-key cryptosystem. A few examples of hard problems are the Traveling Salesman Problem, the Integer and Mixed Integer Programming Problem, the Graph Coloring Problem, the Hamiltonian Path Problem and the Satisfiability Problem for Boolean Expressions. A good introduction to this topic may be found in [AHU74].

The Traveling Salesman Problem is to find a minimal length tour among a set of cities, while visiting each one only once.

The Integer Programming Problem is to solve a Linear Programming problem where some or all of the variables are restricted to being integers.

The Graph Coloring Problem is to determine whether a graph can be colored with a fixed set of colors such that no two adjacent vertices have the same color, and to produce such a coloring.

The Hamiltonian Path Problem is to decide if one can traverse a graph by using each vertex exactly once.

The Satisfiability Problem is to determine whether a Boolean expression in several variables has a solution.

Another hard problem is the Knapsack Problem, a narrow case of the Subset Sum Problem (see Question 2.3.11). Attempts have been made to make public-key cryptosystems based on the knapsack problem, but none have yielded strong results. The Knapsack problem is to determine which subset of a set of objects weighing different amounts has maximal total weight, but still has total weight less than the capacity of the "Knapsack."

Top of the page