1
$\begingroup$

Let $A$ and $B$ be two decision problems in $NP$. Consider three cases:

(1) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having exactly the same number of solutions as $A$.

(2) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having a fixed number of solutions for every solution of problem $A$. We can, in polynomial time, calculate the number of solutions for $A$ provided an oracle that gives the number of solutions to $B$, and vice versa. What if we can guarantee that the number of solutions for an instance of $A$ will be greater than the number of solutions for the corresponding instance of $B$ or vice versa?

(3) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having a solution if and only if $A$ has a solution. However, we do not have a polynomial time algorithm to compute the number of solutions for $A$ provided some number of solutions for $B$. We also cannot guarantee that such a polynomial time algorithm does not exist.

What formal names and notation for the above sort of reductions? When is a Levin reduction called parsimonious? Instances one and two only? Is the third example necessarily worth anything?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

  1. Parsimonious reduction.

  2. Polynomial-time Turing reduction (a.k.a. Cook reduction).

  3. Polynomial-time many-one reduction (a.k.a. Karp reduction).

I've not come across cardinality restrictions of the form you mention in (2) so I don't know any name for them. If you find there isn't a name already, "monotone" would be a good one to choose. In the case where the number of solutions to $B$ is less than $A$, you need "less than or equal to" since, if $A$ has exactly one solution, you still need to reduct it to a "yes" instance of $B$.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I'm on board with your answers for the first two instances, however your answer for instance three is confusing to me. I thought for Karp reductions, a special sort of Cook reduction, one needed to have some way of computing the certificates for $A$ provided some number of certificates for $B$? From your answer, it seems like this is unnecessary and that it also need not be the case that such an algorithm exists? For instance, what if one certificate count from $B$ could map to two certificate counts from $A$? $\endgroup$
    – user26418
    Jan 5, 2015 at 9:48
  • $\begingroup$ Also, why isn't (2) a Karp reduction? I note here that one can produce an instance of $A$ for an instance of $B$ and vice versa, which is a stronger statement than "I can solve $A$ with some number of oracle calls to $B$"? $\endgroup$
    – user26418
    Jan 5, 2015 at 9:50
  • $\begingroup$ @user26418 No, there's no requirement that certificates be "translatable" (for want of a better word) in Karp reductions: Karp reductions don't even require a concept of certificate. My tiny understanding of Levin reductions is that they have the requirement of being able to translate certificates. $\endgroup$
    – David Richerby
    Jan 5, 2015 at 9:51
  • $\begingroup$ @user26418 In a Karp reduction, you construct an instance, call the oracle and return the oracle's answer without further computation. It seems that your case (2) allows extra computation after the oracle call, so it's not a Karp reduction. (For example, "B has twice as many solutions as A so I'll divide the answer by two.") $\endgroup$
    – David Richerby
    Jan 5, 2015 at 9:54
  • $\begingroup$ That's very helpful to know. So a Cook reduction differs from a Karp reduction because it allows for extra computation after an oracle call, necessary if the certificate counts fail to match up for $A$ and $B$. So now, putting this all together, if we have a special case of a Karp reduction that allows for us to recover certificates from problem $A$ provided some number of certificates from problem $B$ in polynomial time, is this a "Karp-Levin polynomial-time many-one reduction"? $\endgroup$
    – user26418
    Jan 5, 2015 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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