Reducibility & Advanced Undecidability

the direction of a reduction

Direction is the make-or-break detail of every hardness proof, and it is where careful students still slip. The slogan is: to prove your problem B is hard, reduce a known-hard problem A to B, not B to A. Picture it as borrowing strength. If a strong friend (the known-hard problem) can lift any weight only by handing the bar to you, then you must be at least as strong as they are. You did the lifting; their power flowed through you.

Here is the logic spelled out. Suppose A is already known to be undecidable, and you build a reduction A <= B. That reduction means: a solver for B would yield a solver for A. But A has no solver. Therefore B can have no solver either, so B is undecidable. The known-hard problem A is the source, your target problem B is the destination, and difficulty flows from A into B. Now reverse it and see why the wrong direction proves nothing: if you instead show B <= A, you have only shown that A could solve B, which (since A is unsolvable) tells you absolutely nothing about B. You learned that B is no harder than something impossible, a vacuous statement.

A reliable mantra: reduce FROM the problem you already know is hard, TO the new problem you want to indict. The known-hard problem is always the one being translated away; the new suspect is always the destination. Phrased with the <= symbol, you want A <= B with A the established-hard problem. The exact same discipline governs NP-completeness later, where you reduce a known NP-complete problem (like 3-SAT) to a new candidate to prove the candidate NP-hard; only the resource being tracked changes.

To prove the emptiness problem E_TM (does machine M accept nothing?) is undecidable, you reduce the known-undecidable A_TM to it: A_TM <= E_TM. You do NOT try E_TM <= A_TM, which would only show E_TM is no harder than an unsolvable problem and prove nothing about E_TM.

Difficulty flows from the known-hard source into your new target: reduce A (hard) to B.

Mixing up the direction is the number one error. Always ask: am I translating the known-hard problem INTO my new problem? If you translate your new problem into the hard one, you have proved nothing about your new problem.

Also called
which way to reducereduce FROM the hard problem歸約的方向