3
$\begingroup$

I find the word "reducible" used in complexity theory not very intuitive, and too general taken on a face value.

What does it exactly mean by problem A reducible to B?

  • Does it mean that A can be reworded into B? i.e. Finding Vertex Set is actually the same as finding an independent set?

  • Does it mean that an algorithm that solves problem B will solve A? i.e. An algorithm that finds longest path will in fact also find the shortest path?

  • Does it mean that A can be proved to be in the same complexity class as B? i.e. A is NP-Hard, B is NPC, then if A is reducible to B, A is in fact NPC?

In other words, A is reducible to B, what can we say about A or B?

As you can see my understanding is quite flaw at the moment, can someone please clarify the application of the word for me maybe even rephrase it into something more intuitive?

$\endgroup$
1
  • 1
    $\begingroup$ This is integral to the definition of NP-completeness and hence dealt with in detail in our reference post. (I don't know which material you are learning from, but I recommend you start absorbing the formal definitions and theorems. You can't do complexity theory without them.) $\endgroup$ – Raphael Dec 3 '14 at 11:40
3
$\begingroup$

The most common notion of reducibility is many-one polynomial time reducibility.

A problem $A$ is many-one polynomial time reducible to a problem $B$ if there is a polynomial time function $f$ such that $x \in A$ iff $f(x) \in B$.

This definition implies that if $B$ is solvable in polynomial time, then so is $A$.

Other notions also exist, but at this stage you're probably better off concentrating just on this one, since it is the one used to define NP-completeness.

$\endgroup$

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