On Friday, July 11, 2003, at 03:44 PM, Dylan Thurston wrote:
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.
Sure, but that doesn't mean that the original problem has to be hard. First of all, the values of N that were bothering David Wilson in the first place were something like a million -- log N is just not that big; we can do a relevant knapsack problem by exhaustion, we just can't do it O(N) times. Second, we just want to know the total number of entries in the NxN mult table, not even test whether any particular number appears or not. And even if answering this led to a knapsack-like solution for some specific number near N, that's fine, by the first point. --Michael Kleber kleber@brandeis.edu