# Reduction as a flowchart

I'm trying to understand the reduction as a flowchart graph. Let's say the boxes $$A$$ and $$B$$ are TMs/Functions and $$x$$ is the input. Is this plot represent reduction from $$A$$ to $$B$$ ($$A\le B$$) or from $$B$$ to $$A$$ ($$B\le A$$)? Or maybe it can be both of the way depending on the context?

## 2 Answers

Let's say that $$f:\Sigma^* \to \Sigma^*$$ is a reduction from $$A\subseteq \Sigma^*$$ to $$B\subseteq \Sigma^*$$. A flowchart graph of $$f$$ looks like: Indeed, $$f$$ maps all words in $$A$$ to $$B$$, and all words in $$\overline{A}$$ to $$\overline{B}$$.

The closest flowchart to the image that you attached corresponds to the reduction theorem, to be explined below. (You explicitly stated that the rectangles in the graph correspond to machines).

The Reduction Theorem: if there is a reduction from $$A$$ to $$B$$, then it holds that i) $$B\in \text{R} \to A\in \text{R}$$, and ii)$$B\in \text{RE} \to A \in \text{RE}$$.

Sketch of The Proof: The proof of the theorem goes as follows. Let $$M_f$$ be a machine that computes a reduction $$f$$ from $$A$$ to $$B$$, and let $$M_B$$ be a machine that decides (recognizes, respectively) $$B$$. Then, a machine $$M_A$$ that decides (recognizes, respectively) $$A$$ operates as follows. On input $$x$$, $$M_A$$ computes $$f(x)$$, and then it simulates the run of $$M_B$$ on $$f(x)$$ and answers the same. The following is the flowchart corresponding to the proof. Note that in both graphs, the arrow is to the rectangle corresponding to the language we are reducing to, $$B$$.

• Thanks great answer! I just wrote a follow-up question to your answer – ChaosPredictor Jan 16 at 15:30

The arrow is going from $$A$$ to $$B$$. It means you are solving problem $$A$$ using problem $$B$$. So, it is a reduction from $$A$$ to $$B$$