[math-fun] NP super-problems
We could solve NP problems if we had an efficient way to calculate either a) F(N,D) = sum(1<=n<=N, 1<=d<=D) floor[n/d] or b) G(N,D) = sum(1<=n<=N) #{ divisors d of N such that 1<=d<=D } "Efficient" means polynomial in the logs of N and D. It's not obvious to me that we could solve these problems even with an NP (or #P) oracle, so perhaps they are stronger than NP. Rich
On Sat, May 24, 2008 at 9:01 PM, <rcs@xmission.com> wrote:
We could solve NP problems if we had an efficient way to calculate either
a) F(N,D) = sum(1<=n<=N, 1<=d<=D) floor[n/d]
or
b) G(N,D) = sum(1<=n<=N) #{ divisors d of N such that 1<=d<=D }
Did you mean "divisors d of (lowercase) n"? I've never seen divisibility associated with NP completeness before; where did these expressions come from? -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
Indeed, Mike's caught a typo. (B) should be "divisors d of n". One NP problem related to divisibility: Does N have a divisor between A and B? Remains NP even if the factorization of N is supplied. The trick is to convert a knapsack problem into this shape. If our knapsack numbers are a,b,c,d,..., and our target is t: We choose a big number X, a smaller number Y, and find primes near X+aY, X+bY, etc. We multiply the primes together to get N. We guess that k of the knapsack numbers will be needed to sum to t, and ask if N has divisors in the range near X^k + t Y X^(K-1). There may be a problem with the time required to find the primes: the expected search time isn't awful, but proving that you'll find them in reasonable time might be too hard. Rich Quoting Mike Stay <metaweta@gmail.com>:
On Sat, May 24, 2008 at 9:01 PM, <rcs@xmission.com> wrote:
We could solve NP problems if we had an efficient way to calculate either
a) F(N,D) = sum(1<=n<=N, 1<=d<=D) floor[n/d]
or
b) G(N,D) = sum(1<=n<=N) #{ divisors d of N such that 1<=d<=D }
Did you mean "divisors d of (lowercase) n"? I've never seen divisibility associated with NP completeness before; where did these expressions come from?
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Mike Stay -
rcs＠xmission.com