P vs NP on TV - Computerphile | Tokyo
Information | History | View | Sightseeing | Video
Audible free book & trial at: http://www.audible.com/computerphile Our thanks to them. P vs NP in The Simpsons and Futurama. Featuring author Simon Singh. http://simonsingh.net Simon on Numberphile: http://bit.ly/SimonSinghPlay Clarification: NP actually stands for non-deterministic (or nondeterministic) polynomial. Simon did us a favour by speaking off-the-cuff on this topic and it is our fault for not cleaning up things in the edit. However Simon's (excellent) book covers this in more detail (pages 157-159 in hard cover) and, in it, he opts for nondeterministic without the hyphen. http://www.facebook.com/computerphile https://twitter.com/computer_phile Film by Sean Riley and Brady Haran. See the full list of Brady's video projects at: http://bit.ly/bradychannels
Comments
-
Simple. The answer is 42!
-
I know an NP-Complete joke, but once you've heard one you've heard them all.
-
Wow, you think very deeply about the Simpsons! I figured ‘P’, ‘NP’ or any other mathematical statement is just there to add effect, rather than a subtle declaration of a philosophical point of view!
-
P = NP ... who's with me?
-
I think he made the Futurama one way more deep than it was. The background is more of the animator's area.
-
Does ANYONE read the existing comments before adding their own?
-
Does ANYONE read the existing comments before adding their own?
-
This video actually explained this problem to me simply! Thanks!
-
Anyone does read their own existing comments before the adding. ;)
-
Does ANYONE read the existing comments before adding their own?
-
Singularity?
-
they cant solve my memes
-
NP doesn't stand for non polynomial it stands for non deterministic polynomial
-
How is it relevant that it appears in culture?
-
0:25 NP is not "Non-polynomial"
-
As a benighted physicist im curious: What about Shor's algorithm which turns prime factorization into a p problem on a quantum computer? Doesn't that show that at least some np problems can become p problems?
-
I knew that NP stands for Non deterministic polynomial time... So a problem that takes polynomial time with a non deterministic machine.
-
p = np but i won't tell.. coz humans are stupid
-
Correct me if Im wrong but I think the increase in time taken for a program to find all factors of a number N could be less than the proportional increase in N ie for large N t1= f (n) t2=f(2n) t2 < 2t1.
My thinking is that first the number of potential primes to check would increase at a slower proportional rate than the size of root N. Bigger than root N don't need to be checked and prime numbers become less frequent the larger you go.
Second if N is a factor of 2 larger it only takes 1 more bit to store it so thats not a problem .
Third the factor test could be done by approximating a number to multiply by and subtracting the multiple from InI until close enough to run through taking the prime from n until n is 0 or negative. The time to check could increase at a slower proportional rate than the size of N and could be roughly proportional to a log function of N so increase at a rate less than root N.
combined for large N you get (less than root N)^2 + log base 2 (N) . -
OSSIPP - Only Simon Singh is pure psychobilly! :>