1
$\begingroup$

Let's say I reduce the problem $A \in L$ to $B \in K$ , with a function $f: \Sigma^{*} \rightarrow \Gamma^{*}$ such that $w \in L \Leftrightarrow f(w) \in K$ . I know if I want to solve $A$, given some polynomial time algorithm for $B$, I just have to transform $A$ to $B$ and solve $B$. So it can be thought as:

The reduction must be done from arbitrary instance of $A$ to a legal instance of $B$

My question is, do I have to reduce to arbitrary instance of $B$ or some instance of $B$? I.e. reduction from TQBNF to Generalized Geography is done to some valid graph instance, but there exist many more valid instances of Generalized Geography.

$\endgroup$
2
$\begingroup$

The mapping does not have to be surjective (onto) nor injective (one-to-one). In fact, any problem that can be solved in polynomial time can be polynomial time many-one reduced to any problem that has at least one accepting instance and at least one rejecting instance: just solve the original problem in polynomial time, then return the accepting instance if the original problem was an accepting instance, or the rejecting instance if the original problem was a rejecting instance.

That said, the Berman–Hartmanis conjecture states that all NP-complete problems are polynomial time isomorphic, meaning that there is a bijective polynomial-time many-one reduction between them with a polynomial-time inverse. This is currently an unproven conjecture, and only refers to NP-complete problems.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So $f$ can be described as a function that can be injective and can be surjective? $\endgroup$ – carpenter Dec 12 '19 at 16:56
  • 1
    $\begingroup$ @carpenter Sure. The definition does not require injectivity or surjectivity, nor does it disallow them. $\endgroup$ – Aaron Rotenberg Dec 12 '19 at 17:00
  • $\begingroup$ Okay, I think I'm closer to understanding this. So if I have a reduction from TQBF (as I mentioned in the question) to some valid graph of GG game, on what basis can I say that in this particular case all instances of GG are PSpace-Hard? Shouldn't only some instances of GG (the one the proof constructs) be PSpace-Hard? $\endgroup$ – carpenter Dec 12 '19 at 17:06
  • $\begingroup$ @carpenter You don't say that instances of GG are PSPACE-hard, you say that the GG problem is PSPACE-hard. Hardness is about problems, not instances; languages, not strings. $\endgroup$ – Aaron Rotenberg Dec 12 '19 at 17:09

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.