Reductions where the number of certificates from one problem can be computed for another to varying degrees

Question

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?

Answer 1

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$.