Using oracle machine to speed up tree solution search

Let $P$ be a boolean problem of size $n$, thus the complete solution search space tree is of size $2^n$. Applying simple tree search for the solution will have take $O(2^n)$ operations, (for simplicity let's assume we do not apply any cuts).

Let $M$ be an oracle machine able to solve a problem $P^\prime$ sub-problem of $P$ of size $k k$?

Possible application of such approach could be solving NP-Complete problems using a quantum computer that is limited to $k$ cubits as oracle machine. Of course it wouldn't solve sub-problem in time of $O(1)$ but it is just for theoretical simplification.

This question was inspired by branch and price algorithm for integer programming, but instead of generating columns, at each node an technically advanced problem solving machine could be applied as an oracle.

Here is an algorithm that will work in some cases: guess the first $n-k$ bits of the solution; fix them; and then solve the sub-problem where you ask what the remaining $k$ bits are. In other words, iterate over all $2^{n-k}$ possibilities for the first $n-k$ bits, and for each such choice, use your oracle to find the remaining $k$ bits.

This works assuming fixing some bits of the problem leads to a sub-problem of the sort that can be solved by your oracle.

(I'm also assuming you can verify whether a candidate solution is correct in $O(1)$ time, you can find a correct solution in $O(2^{n-k})$ steps. This seems to be required to achieve your $O(2^n)$ running time for tree search. If the problem is in NP, then there's a way to verify in polynomial time, so instead of $O(2^{n-k})$ you have $O(2^{n-k} \cdot \text{poly}(n))$.)

StackExchange Computer Science Q#60642, answer score: 2