1
$\begingroup$

I'm trying to understand the reduction as a flowchart graph. enter image description here

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?

$\endgroup$
0
1
$\begingroup$

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:

enter image description here

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. enter image description here

Note that in both graphs, the arrow is to the rectangle corresponding to the language we are reducing to, $B$.

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

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$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.