Let A and B be two decision problems in NP. Consider three cases: (1) For any in
ID: 649781 • Letter: L
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?
Explanation / Answer
Parsimonious reduction.
Polynomial-time Turing reduction (a.k.a. Cook reduction).
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.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.