2
$\begingroup$

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

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

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ 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. $\endgroup$
    – Rick Decker
    Jan 26, 2018 at 20:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Jan 26, 2018 at 22:32
  • $\begingroup$ @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. $\endgroup$
    – Raphael ♦
    Jan 27, 2018 at 0:39
  • $\begingroup$ "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. $\endgroup$
    – Raphael ♦
    Jan 27, 2018 at 0:40
  • 1
    $\begingroup$ thanks for the comments everyone, these are all helpful suggestions, I'll ask the TA on monday to get a certain answer $\endgroup$
    – zython
    Jan 27, 2018 at 15:54

2 Answers 2

Reset to default
3
$\begingroup$

When proving that a problem is NP-hard, we usually reduce another problem, already known to be NP-hard, to out problem. This process must start somewhere - there must be a first problem which is proven to be NP-hard. For this first problem, say SAT, we need to show that every problem in NP can be reduced to SAT. This is the master reduction, which reduces an arbitrary problem in NP to SAT. Following that, we use reductions that reduce a single problem to the problem at hand.

The name master reduction is perhaps common in Germany, but I have never heard of it. In any case it's just an informal name. Just like the fundamental theorem of algebra is some theorem that somebody at some point decided to call that way, so master reduction is just a term that somebody invented for some reason. I have tried to explain the significance of the term above, but in reality there is no higher significance to the term beyond the particular object it refers to.

Improve this answer
$\endgroup$
0
$\begingroup$

The way I understood it is with a master-reduction we dont know how a language looks like, so we take all languages from a set and reduce them onto something else.

Say we want to show that a problem is PSPACE-complete.

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.

Edits and corrections are welcome.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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