[Solved]: When are 2 decision/optimization problems equivalent?

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 AC⁰. 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