# NP-hard problem Reduction of problem $A$ to problem $B$ is an algorithm that transform an instance of $A$ to an instance of $B$ s.t. solving $B$ solved $A$. This defines partial order between problems and is notate by $A\le B$. This can be read as $B$ is a harder than $A$ because solving it drive also solving $A$ but not the other way around. A problem is harder if solving it allow you to solve many other problems. note that if $A\le B$ and $B\le A$ then $A\sim B$ have equivalent hardness. NP-hard problem is a problem that is harder than any [[NP problem]] i.e., $B\in \text{NP-hard}$ if $\forall A\in NP$ satisfies $A\le B$. The Boolean formula satisfiability problem (SAT) is NP-hard because any problem in NP can be verified efficiently and this process can be reduced to a computer simulation. This can be reduced to logical circuit which can be reduced to a (very large) SAT instance. This means $\forall A\in NP$ we have $A\le SAT$. These type of problems have the property that their search space increase exponentially as the problem size increases and there is no known efficient algorithm that can find the solution in the search space in a polynomial time. Why do not we have those efficient algorithm? one option is that they do not exist. There is still no non-existence theorem. Another option is that it exist but we did not find it yet or never will.[^1] It is common to show that a problem is NP-hard by providing a reduction from another NP-hard problem e.g., a problem from [[NP-Complete problem|NP-Complete class]]. The [[Shortest Vector Problem (SVP)]] is NP-hard (we just claim this for now) but not NP because given a shortest vector candidate there is no known efficient algorothm to verify it is really the shortest. This is true to many optimization problems. #tech ## Created 2023-04-23 13:36 [^1]: based on [Alon Amit in quora](https://qr.ae/p2MiSY)