# Strategy to reduce between decision problems

I'm very new to complexity theory, please help me fill in the gaps in whatever knowledge I have acquired till now.

A decision problem is a problem $$X(D)$$ that outputs for each input instance $$I$$, a Yes or No. $$I$$ is called Yes instance if $$X(D) (I)$$ is Yes, No otherwise.

Is my above definition of a decision problem correct? ............... $$(1)$$

$$\underline{Reduction}$$

To reduce a decision problem $$D_1(D)$$ to another $$D_2(D)$$, we have to show $$D_1(D)\leq_p D_2(D)$$, that is,

I need to define a ONE-ONE transformation $$f: \{\text{set of input instances of D_1(D)}\} \to \{\text{set of input instances of D_2(D)}\}$$ such that:

a) $$f$$ transforms in polynomial time in the length of instance $$I_1$$ of $$D_1(D)\;\;\;\;$$

b) $$I_1$$ is a Yes instance of $$D_1(D)$$ if and only if $$I_2 = f(I_1)$$ is a Yes instance of $$D_2(D)$$.

is my above definition/strategy of reduction correct? ............... $$(2)$$

is "polynomial time in the length of instance $$I_1$$ of $$D_1(D)$$" in point a) correct? ............... $$(3)$$

is the requirement that $$f$$ must be one-one also correct? I have missed this keyword in most textbooks I have referred to but I believe it has to be one one since point b) is if and only if condition. ............... $$(4)$$

Could someone please clarify my questions $$(1)-(4)$$?

• "A decision problem is a problem ... that outputs...". It doesn't make sense to say that a problem outputs something. Algorithms can have an output, problems cannot. A decision problem can be identified with a language, i.e., a subset of $\Sigma^*$, where $\Sigma$ is an alphabet. Sometimes a decision problem is defined as a triple $\langle I, S, \pi \rangle$, where $I \subseteq \Sigma^*$ is a set of instances, $S : I \to 2^{\Sigma^*}$ maps each instance to a set of possible solutions... Dec 2 '21 at 15:05
• ...and $\pi$ is a predicate such that, for a $x \in I$ and $y \in S(x)$, $\pi(x,y) = \text{true}$ if $y$ is an actual solution for $x$, and $\pi(x,y)=\text{false}$ otherwise. Solving a decision problem amounts to deciding, for a given $x \in I$, whether there exists $y \in S(x)$ such that $\pi(x,y)=\text{true}$. See, e.g., Section 3.3 in the book "Introduction to the theory of complexity" by D. P. Bovet, and P. Crescenzi. Dec 2 '21 at 15:12