Search code examples
complexity-theoryreduction

What is intuitive explanation of 'reduction from A to B'?

I'm now studying complexity theory and just meet 'a mapping reduction'.

I understand 'polynomial-time reduction from A to B' as 'If one can solve B and have polynomial time, one can solve A.' (Am I right?)

It implies problem A is not harder than (with polynomial time) B.

Then, what is reduced from A to B? How can I understand the word 'reduction'?

Solution

  • Let's assume that the problem A is "to have a cup of coffee". There are many ways to solve this problem, which depend on what you already have:

    • Get into your car, go to the store, buy a bug of coffee, a coffee machine and a cup, get home, power your new machine on, get water, grind coffee etc.
    • Buy a car, then see above
    • Get a credit card, go to Amazon, find a coffee machine, order it, find a cup at home, wash it etc.
    • Apply for a credit card, wait, then see above
    • Go to Starbucks, order a coffee, wait for a seat, etc

    In all these cases you've reduced your problem to a sequence of known steps (sub-problems). If you know, how to solve these sub-problems in reasonable time, and their number is not too large, then you can solve your problem in reasonable time.

    Enjoy your cup of coffee!