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)$


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)$?

  • $\begingroup$ "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... $\endgroup$
    – Steven
    Dec 2 '21 at 15:05
  • $\begingroup$ ...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. $\endgroup$
    – Steven
    Dec 2 '21 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.