Jason (jcreed) wrote,
Jason
jcreed

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} 
Tags: april fools, math
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 1 comment