Proofs of reduction of any hard problem

Question

Approach:1 To prove any unknown problem $B$ is NPH then take any known NPH problem $A$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $A$, then prepare another instance example $I_2$ of $B$, and if $I_2$ can be solved in polynomial time then $I_1$ can be solved in polynomial time, then we say
$$A\leq_m B.$$

Approach:2 Define the function $f\colon \Sigma^*\to \Sigma^*$ as $$ f(x) := \begin{cases} 1,& \text{if}\ w\in A,\\0,&\text{if}\ w\not\in A.\end{cases} $$ Thus, $f$ is a computable function. Also, $w \in A$ if and only if $f(w) = 1,$ which is true if and only if $f(w)\in B.$ Hence, $A\leq_m B.$

My question is:

Are both approaches are right for reduction? What is the difference between them? According to me, Approach:1 is uses for hard problems, and Approach:2 uses for decidable problem.

I am struggling to understand difference between these.

Answer 1

The first "approach" is the definition of a polynomial time many-one reduction. This is the type of reductions used for defining NP-hardness: a problem $B$ is NP-hard if for every problem $A$ in NP, there is a polytime many-one reduction from $A$ to $B$.

The second "approach" is the definition of a computable many-one reduction, which is used to define hard problems for the arithmetical hierarchy.

There are many other notions of reductions that appear in computability theory and complexity theory. The most common are oracle reductions, logspace reductions, and $\mathsf{AC^0}$ reductions.

In fact, there are two orthogonal dimensions here: one is whether the reduction is many-one or oracle, and the other is whether there are any bounds on the complexity of the reduction: computable, polytime, logspace, or $\mathsf{AC^0}$. A third orthogonal dimension is randomization: sometimes we allow our reductions to be randomized.

The notation $\leq_m$ is usually used in contexts in which it has a clear meaning. If you are discussing both computable many-one reductions and polytime many-one reductions, you need to use two different symbols, to prevent confusion.

---

Why do we need so many different types of reductions? In order to properly define completeness, we need the reduction to be weak enough, to prevent the concept from trivializing. For example, all non-trivial problems in NP are NP-hard with respect to computable many-one reductions; in order to obtain a non-trivial concept of NP-hardness, we need to make the reductions weaker than NP.

On the other hand, if the reduction is too weak, then we might have no hard problems, or only few hard problems. Many NP-hard problems are actually hard with respect to reductions weaker than polytime, so it's not immediately clear that the "correct" definition of NP-hardness is with respect to many-one reductions.

A separate issue is whether we should use many-one reductions or oracle reductions. If we used oracle reductions, we couldn't distinguish NP from coNP, for example. Nevertheless, in some cases we are only able to prove that certain problems are NP-hard with respect to oracle reductions (usually known as Turing reductions in this context), which is better than nothing.

---

Which reduction should we "use"? If you want to prove that a language is NP-hard, you should use a polytime many-one reduction, since this is the most general type of reduction for which the proof scheme mentioned in your post works. In other settings you should use other types of reductions, depending on the setting.