[Solved]: What is it called when two problems are similar?

Problem Detail: 

Suppose that there are two problems $P$ and $Q$.

How can I say that "solving $P$ is same thing with solving $Q$"?

For instance, if $P$ is NP-Hard, then we can say "$P$ can be solved in polynomial time iff there exists an algorithm $A$ that solves $Q$ in polynomial time".

There should be a shorter term for this, and I'm sure that is not similar.

Is equivalent the right word?

Asked By : cagirici

Answered By : Yuval Filmus

In complexity theory we prefer, when possible, to use formal definitions. Two problems $P,Q$ are polynomially equivalent if there are polytime functions $f,g$ such that $x \in P$ iff $f(x) \in Q$ and $y \in Q$ iff $g(x) \in P$. This is the usual notion of equivalence in complexity theory.

Sometimes we prefer a coarser notion of equivalence which allows using a problem as an oracle. Two problems $Q,R$ are polynomially equivalent with respect to oracle reductions if $Q \in \mathsf{P}^R$ and $R \in \mathsf{P}^Q$, or in other words, $Q$ can be solved in polynomial time with oracle access to $R$, and $R$ can be solved in polynomial time with oracle access to $Q$. Under this notion, 3SAT and co-3SAT (its complement) are equivalent.

Unless I have made a blunder, both these notions are equivalence relations. In both cases, if one problem can be solved in polynomial time, then so can the other. Since the second is more general, it seems to fit your description better, though in complexity theory we usually prefer the finer first notion, or even finer notions such as logspace reducibility and AC⁰ reducibility.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35346

 Ask a Question

 Download Related Notes/Documents