RSA Laboratories

2.3.1 What is a hard problem?

Public-key cryptosystems (see Question 2.1.1) are based on a problem that is in some sense difficult to solve. Difficult in this case refers more to the computational requirements in finding a solution than the conception of the problem. These problems are called hard problems. Some of the most well known examples are factoring, theorem-proving, and the Traveling Salesman Problem (see Question 2.3.12).

There are two major classes of problems that interest cryptographers - P and NP. Put simply, a problem is in P if it can be solved in polynomial time (see Section A.7), while a problem is in NP if the validity of a proposed solution can be checked in polynomial time. An alternative definition of NP is found in the glossary (Appendix B). Every problem in P is in NP, but we do not know whether P = NP or not.

For example, the problem of multiplying two numbers is in P. Namely, the number of bit operations required to multiply two numbers of bit length k is at most k2, a polynomial. The problem of finding a factor of a number is in NP, because a proposed solution can be checked in polynomial time. However, it is not known whether this problem is in P.

The question of whether or not P = NP is one of the most important unsolved problems in all of mathematics and computer science. So far, there has been very little progress towards its solution. One thing we do have is the concept of an NP-complete problem. A problem X in NP is called NP-complete if any other NP problem can be reduced (transformed) into X in polynomial time. If some NP-complete problem X can be solved in polynomial time, then every NP problem Y can be solved in polynomial time; first reduce Y to X and then solve X. The Traveling Salesman Problem, the Knapsack problem, and the Hamiltonian Problem (see Question 2.3.12) are a few NP-complete problems.

To prove that P = NP, it would suffice to find a polynomial-time algorithm for one of the NP-complete problems. However, it is commonly thought that P ¹ NP. If it were to be proved that P = NP, we could potentially solve an enormous variety of complex problems quickly without a significant advance in computing technology (assuming the reductions between different problems are efficient in practice). For more on the theory of computation, we recommend [GJ79] and [LP98].

Top of the page