2

A and B are both problems in NP. Does a function f that transforms any instance of A into an instance of B and function F that transforms the solution to that instance of B into solution to problem A exist?

Basically, is the following true? $$A,B \in NP$$ $$\{ \exists f,F\ |\ A(x) = F(f(A(x))),\ f(A(x))=B(y)\}$$

This answer indicates that polynomial reduction is possible if both A and B are in P and I'd like to know it something similar occurs in NP as well.

I'm aware that a polynomial reduction would mean P=NP (and vice versa) and that a reduction of problem in NP to a problem in NP-complete is possible in polynomial time, but I wonder if even if P $\neq$ NP, some form of transformation is still be possible.

Thank you

Freeman
  • 45
  • 3
    If exponential time is allowed then your transformation of A would be simply to solve it and write B as true is A is satisfiable and false otherwise. Exponential time gives too much power for its reductions be revelatory about NP problems. – Kyle Jones Jun 15 '17 at 01:03
  • @KyleJones - I was wondering about this and the problem probably comes from my lack of knowledge regarding the NP class and complexity in general.$$$$Since NP contains only decision problems, $F$ should be trivial, but how would you construct $f$? It sounds as if you are not even transforming the input for $B$. I was thinking that it might be possible to have a function that solves $A$ and on false constructs input for $B$ that would compute as false and vice versa, but it sounded so silly that I didn't even write it in the original question. – Freeman Jun 15 '17 at 08:49
  • @KyleJones - I was thinking that the proof would be of a similar nature to the one that proves polynomial reduction between P problems, but I wasn't able to find that proof in any detail. It might be that it is of similar nature to what you have alluded to. Thank you for the comment. – Freeman Jun 15 '17 at 10:45
  • @KyleJones Oh, I think I understand now. I've found this answer from Kevin Carlson [tinyurl.com/yaycpxd2]. So, since I need different reduction for each pair of A and B, I can always just get inputs $y$ and $y'$ from B (doesn't matter how difficult that is, as long as it's possible and each problem in NP should have them), where $B(y)$ computes as "yes" and $B(y')$ as "no", then I run $A(x)$ as you have suggested and if I get "yes", I run $B(y)$ else I run $B(y')$ and this will work for every $x$ from A. Is that correct? – Freeman Jun 17 '17 at 13:41

1 Answers1

1

Any problem in NP can be solved in exponential time because $NP\subseteq EXPTIME$.

https://en.wikipedia.org/wiki/EXPTIME

So the answer of this question would be the same as the answer you linked for two problems in P.

Yining Wang
  • 1,279
  • 7
  • 23