2
$\begingroup$

Using the following definition:

Reduction: There is a polynomial-time reduction from problem $X$ to problem $Y$ if arbitrary instances of problem $X$ can be solved using:

  • Polynomial number of standard computational steps, plus
  • Polynomial number of calls to oracle that solves problem $Y$.

Notation $X \leq_{P} Y$

Say we had the case where $X$ can be solved in polynomial time using $O(n\log n)$ of computational steps, with zero calls to the oracle / black box used to solve instances of $Y$.

Can we still say $X \leq_{P} Y$? As 0 still classifies as a polynomial number of calls to the oracle that solves problem $Y$, and a polynomial number of standard computation steps were used to solve $X$.

$\endgroup$
1
  • $\begingroup$ @OliverCharlesworth Will do, sorry! Thanks for the heads up. $\endgroup$
    – JWyatt
    Nov 14, 2014 at 0:55

1 Answer 1

2
$\begingroup$

Yes. As you note, $f(n) = \sum_{i=0}^{k}0\cdot n^{i} = 0$ is a perfectly valid polynomial in $n$ (for every fixed $k$).

What you have left over without the oracle calls is just a polynomial time algorithm. This observation also underlies the fact that any polynomial-time solvable problem has a polynomial-time reduction to any other non-trivial problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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