7
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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 AC0 reducibility.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.