# What is a “Master-Reduction”?

I keep stumbling upon this term in my lecture notes tutorials and assignments, but I have no clue what it means, google doesnt give me anything usable at all.

Here is an example how this term is used (material in german, but self explanatory really)

So my question is: is this a regional dialect or some important technique that I have missed ?

• It appears that the "Master" modifier is a way of emphasizing that every language $L\in NP$ can be reduced to SAT, as the clause immediately below indicates. – Rick Decker Jan 26 '18 at 20:38
• It's not a term I've ever heard in English. I would guess it refers to the fact that SAT is proven NP-complete by reducing the acceptance problem of an arbitrary NP Turing machine to SAT, whereas almost every other problem's NP-completeness proof is by reducing some other NP-complete problem to it. SAT is basically the only problem where we prove literally and directly that every other NP problem reduces to it; for everything else, we do it indirectly. – David Richerby Jan 26 '18 at 22:32
• @DavidRicherby I was told off on another answer once for a similar claim; apparently there are a few direct NP-hardness proofs for other problems. – Raphael Jan 27 '18 at 0:39
• "Master-reduction" may be hinting at the proof technique: we'll describe one "meta" reduction (technique) by which can can reduce each such L to SAT. The claim that we need such a "master" reduction is bold; there may be other proofs. – Raphael Jan 27 '18 at 0:40
• thanks for the comments everyone, these are all helpful suggestions, I'll ask the TA on monday to get a certain answer – zython Jan 27 '18 at 15:54

We take any language $L\in PSPACE$ and reduce them onto our problem, since we often can easily show that a problem is contained in $PSPACE$ and we've shown in the last step that any language $L\in PSPACE$ can be reduced onto our problem we have shown that our problem is $PSPACE$-complete.