simrob pointed out that yesterday Doron Zeilberger posted a great April Fool's solution to P=NP. What I like about it is how it starts off completely reasonably, and uses generatingfunctiony polynomials in a really cute way.Here I pose several queries to mathematica as to how many solutions there are to subset-sum for when my set is {1,1,4} and my target sum is one of 0,1,2,3,4,10.
p = (1+x)(1+x)(1+x^4);
Map[(1/(2 Pi)) Integrate[(p / x^#) /. x -> Exp[I u], {u, -Pi, Pi}]&, {0,1,2,3,4,10}]
and lo and behold it correctly yields:
{1, 2, 1, 0, 1, 0}
---
Oh, oops, I should really have been using NIntegrate to do numerical integration. It yields (still correct out to 16 decimal places, very impressive!):
-17 -16 -16
Out[36]= {1. - 7.0679 10 I, 2. + 2.56211 10 I, 1. + 3.53395 10 I,
-16 -17 -16
-7.44338 10 - 1.98785 10 I, 1. - 3.71065 10 I, 0. + 0. I}