Given a bound, $B$, and a list of (small) primes $(p_0, p_1, \dots, p_{n-1})$ is there an efficient algorithm to find the next number greater than $B$ that can be expressed as a product of primes from the list?
More formally, given
$$B = 2^\beta$$ $$(p_0, p_1, \dots, p_{n-1}),\ \ p_i < poly(\beta)$$ can one find $$min_{ q - B > 0 }(q-B), \ \ q = \prod_{i=0}^{n-1} p^{\nu_i}_i $$
in time/space $O( poly(\beta, n) )$? Even pointers to literature would be helpful...
Note: I saw the Polymath paper on deterministic prime finding in an interval ( Deterministic methods to find primes ) and thats what inspired this question. It's superfluous to have the list be primes, but I've kept it in for simplicity.
Also note that this is a slightly more cleaned up version of this post on cstheory.stackexchange.com.