Reduction Transitive Relation Problem

Question

I have this problem on my homework, it's my last one left but I'm having trouble with it. Any help would be appreciated.

Answer 1

Here is the answer to the question, a lot simpler than I thought..

Answer 2

If I understand that correctly, this is what we're trying to prove:

If problem $P_1$ is reducible to $P_2$ in polynomial time, and $P_2$ is reducible to $P_3$ in polynomial time, then $P_1$ is reducible to $P_3$ in polynomial time.

This follows from the fact that a composition of two polynomials must be a polynomial. You can prove this very easily, if the fact that it is intuitively clear is not enough.

I hope I answered your question.

Answer 3

Definition:

Let $P_1$ and $P_2$ be two problems and $\mathbb{A}$ be the space of all poly-time algorithms, then

$P_1 \leq_P P_2$ if $((\exists \ A_1,\ A_2 \in \mathbb{A}): (A_1 \text{ maps any instance } I \text{ of } P_1 \text{ to an instance } A_1(I) \text{ of } P_2) \text{ and } (A_2 \text{ maps any solution } S \text{ to } A_1(I) \text{ to a solution } A_2(S) \text{ to } I))$

Proposition:

Show that

$$P_1 \leq_P P_2 \text{ and }P_2 \leq_P P_3 \Rightarrow P_1 \leq_P P_3$$

Proof:

Assume that $P_1 \leq_P P_2 \text{ and }P_2 \leq_P P_3$

By def. $(\exists\ A_1,\ A'_1,\ A_2,\ A'_2 \in \mathbb{A}): (A_1(p_1) = p_2 \text{ and } A'_1(s_{p_2})=s_{p_1}) \text{ and } (A_2(p_2) = p_3 \text{ and } A'_2(s_{p_3})=s_{p_2})$

Illustration:

The goal is to show the existence of two poly-time algorithms which satisfy the definition of reduction. Formally, we need to proof $(\exists\ A,\ A' \in \mathbb{A}): A(p_1) = p_3 \text{ and } A'(s_{p_3}) = s_{p_1}$

$A(p_1) = p_3 \Leftrightarrow A(p_1) = A_2(p_2) \Leftrightarrow A(p_1) = A_2(A_1(p_1)) $

As you can see $A$ maps $p_1$ to $p_3$

Since $A_2 \in \mathbb{A}$, then $A \in \mathbb{A}$, That is, $A$ is a poly-time algorithm.

Again we have $A'(s_{p_3}) = s_{p_1} \Leftrightarrow A'(s_{p_3}) = A'_1(s_{p_2}) \Leftrightarrow A'(s_{p_3}) = A'_1(A'_2(s_{p_3}))$ So $A'$ maps $s_{p_3}$ to $s_{p_1}$ Since $A'_1 \in \mathbb{A}$, then $A' \in \mathbb{A}$, That is, $A'$ is a poly-time algorithm.

Illustration: