Right. Define L = (a+b)/2 and R = (a-b)/2, so that a * b = L² - R² for all a, b. If there exist positive integers a, b such that a * b = n with |a-b| <= k n^(

Right. Define L = (a+b)/2 and R = (a-b)/2, so that a * b = L² - R² for all a, b. If there exist positive integers a, b such that a * b = n with |a-b| <= k n^(1/4) [constant k] Then there exist L, R (either both integers or both half-integers) with L² - R² = n and |R| <= (1/2) k n^(1/4) From which one can deduce: R² <= (k²/4) √n L² - R² >= L² - (k²/4) √n n >= L² - (k²/4) √n L² <= n + (k²/4) √n L <= √(n + (k²/4) √n) L <= √n + k²/8 If k <= 1, then L must be ceil(√n) or ceil(√n) - 1/2 If k <= 2√2, then L must be ceil(√n), ceil(√n) - 1/2, or ceil(√n) + 1/2 (my original estimate of 2 steps was due a slight miscalculation) Adding epsilon would re-introduce an exponential component to the search. In fact, epsilon = 3/4 gives you total power. But this is only relevant if the reduction (https://cstheory.stackexchange.com/a/4785 https://cstheory.stackexchange.com/a/4785) can be made precise enough to bound L, U to within a fixed small epsilon. It could even be the case that you can bound to an arbitrarily small epsilon, but only at the expense of exploding other parameters. (B, T, k).