# Search reduction to decision

I'm a little stumped on this question (and I don't know the name of it, which is why I've excluded it from the title). I need to describe an algorithm that finds a solution to an NP-Hard problem given an oracle that can solve the decision problem. Here is the problem :

Suppose two $$n\times2$$ arrays $$A$$ and $$B$$ represent sales amounts for two products A and B respectively. In year $$i$$, strategy 1 sees A sell $$A[i]$$ units and B sell $$B[i]$$ units; similarly, in strategy 2, A sells $$A[i]$$ units and B sells $$B[i]$$ units. A long-term strategy, $$L$$, is an $$n$$-element array $$S$$, where $$S[i]$$ denotes the chosen strategy for year $$i$$ (i.e. if $$S[i] = 1$$, then strategy 1 is chosen for year $$i$$).

The goal is to minimise the difference in sales figures between product A and B over an $$n$$ year period. We want to find if the absolute difference between sales figures is less than some value $$s$$:

$$\left |\sum_{i=1}^nA[i][L[i]] - \sum_{i=1}^nB[i][L[i]] \right| \leq s$$

An oracle exists that can solve any instance of the decision problem. It takes $$A, B, s$$ parameters, returning TRUE if a solution exists for the inputs. Write an algorithm that outputs a long-term strategy $$L$$ with an imbalance of at most $$s$$ if one exists, using the oracle. Analyse time complexity.

I've already proven that the problem is NP-hard, by proving a polynomial-time Karp reduction from the Partition problem. I'm not sure where to go from here...

• Have you seen any examples of search-to-decision reductions? Try to follow them. Usually you guess a small part of the solution, and use the decision oracle to check whether the guess leads to a solution. If so, you simplify the instance, and repeat. – Yuval Filmus May 5 '20 at 7:46