# Hard computation problems What is meant for a computation problem to be hard? How to identify that a problem is a hard? Can it be proven that a problem is hard? What is their usefulness? You can think of a problem as given a description of what you are looking for in a large space. A solution is an efficient algorithm that solve it i.e., it travel through the space of possibilities in some efficient path that ends at the searched element. By "efficient" we mean that the "path" (number of steps of the algorithm) is not much larger than the problem description. An inefficient solution always exist - traverse the entire space until you reach the searched element. In contrast, a problem is hard if there is no efficient known algorithm that solves it although many smart people that dedicate long time to try and solve them. Most common hard computational problems do not have a logic proof that there is no efficient algorithm for them. This means that we can't know for sure if a problem is really hard because maybe tomorrow an efficient algorithm will be found. This happened in the past, for centuries the problem of deciding if a number $N$ is prime (i.e., find a factor in the space of all numbers smaller than $N$) was considered hard but in 2002 an efficient algorithm was found - the [[AKS primality test|AKS algorithm for primality]]. Proof for hardness might be found in the future as was the case in Mathematic where conjectures that were not proven for decades and even millennia were solved unexpectedly e.g., [[Poincare Conjecture]] ,[[Squaring the circle problem]] and Fermat's last theorem. In 1971, Stephen Cook and Leonid Levin came with three important observations: 1) many interesting problem have a [[NP problem|common property]]: they have an efficient procedure for verifying a proposed solution 2) a problem $A$ can be reduced to another problem $B$ such that solving $B$ will enable solving $A$. This create partial order between problems 3) problems with efficient verification procedure can be reduced to a single common problem: the Boolean Formula Satisfiability Problem (SAT). This means solving SAT will instantly solve the other problems. This makes SAT the hardest problem in this class. Any problem that is reduced from SAT is also hardest. This defines a class of hard problems that is called [[NP-Complete problem|NP-Complete]] . This is a new type of definition for problem hardness - a problem is hard if solving it allow to solve instantly many other hard problems. This is the basis of Complexity theory - the theory of classifying problems according to their hardness. Hard computation problem are the basis of modern cryptography: the basic idea is to prove that breaking a cryptography scheme is equivalent to solving a very hard problem. If you know that a problem is hard you know that your scheme is secured. Computation problems solving is strongly related to technology. Algorithms are the language that describe how problems are solved. Problem hardness is defined by the number of operations and resources are needed for their solution. Advance in algorithms caused some problems that were considered as hard in the past to become simple to solve. New technologies can solve efficiently problems that are hard to solve with previous technology. For a example, quantum computers can solve the inverse log problem, factoring large numbers exponentially faster than existing classical computers. They can also search quadratically faster. It can be hard to generate hard instance of hard problem (a key problem for cryptography). Being able to come with hard problem instances is possible for lattice problem as found by Ajtai. Some problem can be hard in worst case instances and easy to solve on average instance (random instance?). Some lattices problems have this property. ## Questions - why lattice problem are hard? are they are NP-hard? NP-complete? - examples of hard problems - full secrecy with one-time pad - how this relate to hardness? ## Created 2026-04-24 10:28