## Global Sales Contact List

Contact   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• 1-781-515-5000
RSA LABORATIORIES
11 Cambridge Center
Cambridge, MA 02142 - USA

# 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

Notes:
Connect with EMC
Need help immediately? EMC Sales Specialists are standing by to answer your questions real time.
Use Live Chat for fast, direct access to EMC Customer Service Professionals to resolve your support questions.
Explore and compare EMC products in the EMC Store, and get a price quote from EMC or an EMC partner.
We're here to help. Send us your sales inquiry and an EMC Sales Specialist will get back to you within one business day.
Want to talk? Call us to speak with an EMC Sales Specialist live.
Share & Follow