Polynomial Time Reduction - Does 0 calls to the black box still imply a reduction?

Question

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$.

Answer 1

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.