# 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 (finite) space. A solution is an efficient procedure (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. note that inefficient solution always exist - just traverse the entire space until you reach the searched element. This is called brute-force solution. A problem is considered hard if no efficient solution is known although many smart people tried very hard to find one. 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 hard in principle or that efficient algorithm just had not been found yet. Finding efficient solution to problem that were considered hard in the past had happened many time 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 [[PRIMES is in P (AKS primality test)|AKS algorithm for primality]]. Another example is the problem of finding factors of a number. This problem was considered hard for centuries and was the basis for the [[RSA - public key encryption|RSA]] public key cryptography. But, In 1994 Peter Shor showed that there is a [[Shor's factoring algorithm|quantum algorithm]] that finds factors efficiently. BTW, this algorithm was extended to solve other problems that were considered hard and where the basis of the entire encryption of the internet. This means that once a quantum computer will be available - the internet encryption will be breakable. It is interesting to compare problems to mathematical-theorems and solutions to mathematical-proofs. A proof is analog to an efficient solution. The problem of verifying a proof can be efficiently solved: the algorithm verify that each step in the prove is justified from a finite set of logical laws and that the final step is the theorem. note that this problem is different from the problem of finding a proof. The solution space of all possible proofs is infinite (proof size is finite but there is no bound on its size) while the solution for a problem as we define it is finite. maybe very large - but finite. This makes brute force for finding proof of a theorem impossible for some theorems. We can generate all proofs with increasing size and check each one if the last step is the theorem we want to prove or its negation. But, [[Godel's Incompleteness Theorem]] shows that there are theorems that are true but do not have a proof. This means that our process will continue indefinitely as they will not appear as last step (as this will be a proof - a contradiction) and as it true its negation will not appear either. So, we will keep generate larger and larger proofs indefinitely. Hard problems are similar to mathematical conjectures in the sense that it is unknown how to solve a hard problem and it is unknown how to prove a conjecture. This state can continue for long time (centuries) and then one day a proof or disproof is found 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) problems are strongly related: 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) all 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. These became 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. Problems solving is strongly related to technology. 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. worst-case vs. average-case. 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