Problem Detail: Does anybody know a good definition of 2 decision / optimization problems being equivalent? I am asking since for example allowing polynomial time computations any 2 problems in NP could be considered equivalent.
Asked By : Reb
Answered By : Yuval Filmus
Suppose $L_1$ and $L_2$ are two decision problems, and $mathcal{A}$ is a class of algorithms (like $P$). Say that $L_1$ is $mathcal{A}$-reducible to $L_2$ if there is an $f in mathcal{A}$ such that $x in L_1$ iff $f(x) in L_2$. Say that $L_1$ and $L_2$ are $mathcal{A}$-equivalent if each is $mathcal{A}$-reducible to the other. For example, all NP-complete problems are $P$-equivalent. If you want a finer notion, you can consider more restricted classes, such as log-space or even AC0. Such notions of reducibility actually come up in refinements of Schaefer’s dichotomy theorem. As for optimization problems, let’s consider maximization problems. With each maximization problem $L$ (which is a function mapping instances to optimal values), you can associate the decision problem $L’$ consisting of pairs $(x,v)$ such that $L(x) geq v$. Now you can define reducibility and equivalence as before.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6393
