Polynomial Mappings and Direction

## Which way the arrow points Write the relation as `A <=p B`: there is a polynomial-time map sending each instance of `A` to an instance of `B` with the same answer. Read it as **"B is at least as hard as A"**, because a fast algorithm for `B` immediately yields a fast algorithm for `A` — translate, then ask. Everything about direction follows from that single reading. So `yours <=p SAT` reads "SAT is at least as hard as yours". It puts the hardness on the *other* side. The conclusion "therefore mine is hard" is not a small slip in wording; it is the exact inverse of what was constructed. ## Why the inverted proof is empty Mapping into a hard problem is not evidence of difficulty, for a concrete reason: **every problem whose solutions can be checked quickly maps into SAT** — that is what the Cook-Levin theorem established. Sorting-style feasibility checks, reachability questions, trivially easy problems: they all reduce to SAT too. A property shared by the easiest and the hardest members of a huge class separates nothing. The practical smell test is to finish the sentence out loud. "I can rewrite my problem as SAT, therefore ..." only ever completes as "... therefore my problem is no harder than SAT". If the speaker completes it with "therefore my problem is hard", they have swapped the subject. ## The two jobs, and the map each one needs | Your goal | Build a map | It proves / buys | |---|---|---| | Argue nobody should keep hunting for a fast exact algorithm | from a **known-hard** problem **into** yours | yours is at least as hard as that problem | | Reuse an existing, well-tuned engine instead of writing an algorithm | from **yours into** an already-solved problem | yours is no harder than that one; you get a working pipeline | | Show two problems are equally hard | both maps | mutual reducibility | Notice that the two useful jobs point in **opposite** directions, which is precisely why the mistake is so easy to make: the same machinery, the same word "reduce", two incompatible conclusions. ## Doing the hardness argument properly 1. **Pick the source deliberately.** It must be a problem already established as hard, and it should be structurally close to yours, or the construction becomes unmanageable. 2. **Map every instance, not the awkward ones.** The argument covers the whole source problem; a construction that only handles convenient instances proves nothing. 3. **Show both directions of the equivalence.** Source yes-instance produces a target yes-instance, *and* source no-instance produces a target no-instance. 4. **Keep the construction polynomial**, and say so explicitly — this is the step candidates most often leave implicit. ## What interviewers are listening for - Whether you name the **source** and the **target** without hesitating, rather than saying "I reduce them to each other". - Whether you can state, in one sentence, what a fast algorithm for the target would imply about the source. - Whether you notice unprompted that the direction you just described gives an upper bound when you were asked for a lower one. A strong answer sounds like: "To claim my task is hard I would take a known-hard problem and build each of its instances as an instance of my task, in polynomial time, preserving yes and no. Then a fast algorithm for my task would solve the known-hard one, which is the contradiction I want. The map I actually built goes the other way, so all it shows is that my task is no harder than the target." ## The consequence at work The direction is not academic bookkeeping; it changes what a team does next. An upper bound (`yours <=p solved`) is a *build* result: it hands you an implementation path through an existing engine. A lower bound (`known-hard <=p yours`) is a *stop* result: it says a fast exact algorithm for the general case would be a major discovery, so the plan should shift to restricting the input, accepting approximate answers, or exploiting a parameter that stays small. Presenting an upper bound as if it were a lower one sends a team in exactly the wrong direction — it argues for abandoning a search that was never shown to be hopeless.