Using oracle machine to speed up tree solution search

Question

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 < n$ in time $O(1)$

Is there a known approach of applying $M$ during searching for solution of $P$ in order to find it in time $O(2^{n-k})$? If speed-up of factor $O(2^k)$ is not possible, what is the best known achievable result for such problem? Are oracle machines limited to problem size $k$ useful at all to solve problems of size $n > 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.

Answer 1

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

Answer 2

Remarks

Concept of oracle machine has been misunderstood in this question. I should have used term a black-box machine. An oracle does not provide association of values to variables, only yes or no answer which is used for self-reducible problems, which allows to find association of values in polynomial time.

Solution

Such black-box machine would work but is not possible to be constructed for all the problems, does not work in general case.

Every time our black-box provides us with solution to a sub-problem of size $k$ it should modify the instance of the problem to forbid this solution in future runs, otherwise it will loop. For some of the problems such us independent set problem this cannot be done without adding additional variables. Since in worst case scenario there is $O(2^k)$ partial solutions, problem size may grow exponentially making it not solvable.

This is the case of independent set problem but not boolean satisfiability problem since partial solutions can be forbidden by adding additional clauses, not variables.

Other answers

@D.W made a good point and good argument, unfortunately it does not work in general case as explained earlier.