NP-Hard

A problem $X$ is NP-Hard if every problem $Y\in NP$ reduces to $X$.

• If $P\ne NP,$ then $x\notin P$

If $P\ne NP$, then NP-hard problems could not be solved in polynomial time.

Proving Hardness Using $A$ Polynomial Reduction

Activity: Assume problem $A$ is known to be impossible to be solved in polynomial time. True/False: $A{\le }_{p}B\Rightarrow B$ Cannot be solved in polynomial time.

The answer is True. Assume that $B$ can be solved in poly-time with an algorithm. $Al{g}_B$. Use $Al{g}_B$ for solving $A$ by reducing it to $B$. But it is impossible.

Now look at the notation. $A{\le }_{p}B$. B is at least as hard as A, in other words, if I could solve $B$, I could solve $A$. B is harder to solve.

Summary:

In computational complexity theory, when we say that problem $A$ is polynomial-time reducible to problem $B$ (denoted as $A{\le }_{p}B$), it means that we can efficiently transform instances of problem $A$ into instances of problem $B$ in polynomial time. In essence, this reduction implies that if we could solve problem $B$ efficiently (in polynomial time), then we could also solve problem $A$ efficiently by first transforming its instances into instances of BB and then using the polynomial-time algorithm for $B$ to solve them.

ahhhh

Assumption: Let’s assume that problem $A$ is known to be impossible to be solved in polynomial time. This implies that there is no polynomial-time algorithm capable of solving $A$.

Implication: Now, if we have a polynomial-time reduction from $A$ to $B$ (i.e., $A{\le }_{p}B$), and we assume that $B$ can be solved in polynomial time, it would imply that we could solve $A$ in polynomial time as well. This is because we could transform instances of $A$ into instances of $B$ using the polynomial-time reduction and then solve them using the assumed polynomial-time algorithm for $B$.

Contradiction: However, this contradicts our initial assumption that problem $A$ cannot be solved in polynomial time. If $A$ cannot be solved in polynomial time, and we have a polynomial-time reduction from $A$ to $B$, then $B$ also cannot be solved in polynomial time. This is because if $B$ were solvable in polynomial time, we would be able to solve $A$ in polynomial time, which contradicts our assumption about the hardness of $A$.

Therefore, if problem $A$ is polynomial-time reducible to problem $B$ and problem $A$ is known to be unsolvable in polynomial time, it follows that problem $B$ cannot be solved in polynomial time either. This demonstrates how we can use polynomial reductions to infer the hardness of problems and establish relationships between their complexities.