On Sun, Jul 06, 2003 at 02:09:27PM -0400, William Thurston wrote:
Isn't the problem to determine when an n-digit number appears in a multiplication table of side length roughly its square-root presumably NP-complete? This is a variation of the knapsack problem, trying to distribute a bunch of packages into two bags each of which has total weight less than N.
Oh, nice. Yes, that should be right. Explicitly, if d_1, ... d_k are the prime factors of N (with multiplicity), you're trying to divide log d_1, ..., log d_k into two sets, each with sum less than log L (where L is the side length of the table). By picking the d_i appropriately, you can get this to be close to any givn instance of the knapsack problem, which is NP complete; the remaining issue is whether you can do this without making the d_i too large (thus ruining the NP-completeness). The right measure of complexity here is log N or the sum of log d_i. Peace, Dylan