World's most popular travel blog for travel bloggers.

Using oracle machine to speed up tree solution search

, , No Comments
Problem Detail: 

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.

Asked By : Marek
Answered By : Marek


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.


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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback