# 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? 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 might come as a surprise that there in no way to prove that most computation problem are hard. The most one can say is that a problem was not solved efficiently by many smart people that tried their best for long time. maybe even decades. This is of course not a proof. Mathematic has great stories on conjectures (problems) that were not solved for decades and even millennia but one day someone solved them e.g., [[Poincare Conjecture]] ,[[Squaring the circle problem]] and Fermat's theorem. A problem can be transformed to another problem in a way that solving the target problem efficiently enable solving the source problem efficiently. This is called reduction and it creates hierarchy of problems. In 1971, Stephen Cook and Leonid Levin found the Boolean Satisfiability Problem (SAT) that if solved efficiently will solve many natural computation problem. This problem is the hardest problem. Any problem that is reduced from SAT is also hardest. This created a class of hard problems that are called [[NP-Complete problem]] . This is the basis of Complexity theory - the theory of hardness classes for problems. 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? - What are problems? how is this concept defined? - examples of hard problems - full secrecy with one-time pad - how this relate to hardness? ## Created 2026-04-24 10:28