1

Suppose we are given two problems $A$ and $B$ (both are solvable). Is it always possible to transform one of it to another? That means whether holds $A \preceq B, B \preceq A, or A \equiv B$. This should be possible, if $A$ and $B$ are NP problems, but is it still possible, if A and B are not from NP?

Thanks in advance!

El Sablo
  • 11
  • Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – Community Feb 07 '23 at 09:09
  • I don't know what NP is, but maybe the subject of Turing degrees is relevant to your question. Note that there are $c = 2^{\aleph_0}$ many pairwise incomparable Turing degrees. – Dave L. Renfro Feb 07 '23 at 09:26
  • If you can prove this for NP problems and polynomial time reducibility, then you have proved P = NP, because Ladner showed ("On the structure of polynomial time reducibility", J. ACM 22(1):155-171, 1975) that if P and NP are distinct then there are problems in NP which are incomparable w.r.t. this notion of reduction (in fact infinitely many). There are other kinds of reduction though so you should specify which one you care about. – alexg Feb 07 '23 at 10:55

0 Answers0