Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


P vs NP

No description

Malin Christersson

on 25 March 2011

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of P vs NP

P vs NP ...and the Problems are: Birch and Swinnerton-Dyer Conjecture Hodge Conjecture Navier-Stokes Equations P vs NP Poincaré Conjecture Riemann Hypothesis Yang-Mills Theory was solved by Grigoriy Perelman 2003
he didn't claim the prize back then
but got the award 2010 http://www.claymath.org/millennium/ if you prove it's true
you get fame and fortune Publish your solution in a "refereed
mathematics publication" Wait for two years (gain a general
acceptance in the mathematics community) Prove one of them Win the Millenium Prize of $1 million The Millenium Prize Problems computers communicate eavesdroppers listen what to do? the messages are numbers binary encode them! Eve takes two large primes and and computes 100 digits large she then finds a small number relatively prime to Eve tells Adam if you want to send me message ...don't send me ...send me Adam writes his message and computes follows from a generalization of Fermat's little theorem Eve finds http://en.wikipedia.org/wiki/Leonhard_Euler the eavesdropper knows and and the message ...and he knows the scheme the public key RSA cryptography speaking of cryptography It was thanks to Ultra
that we won the war. Winston Churchill http://en.wikipedia.org/wiki/Enigma_machine the eavesdropper listens the eavesdropper listens the public key Eve finds the number use an extension of Euclid's algorithm http://en.wikipedia.org/wiki/File:Sinking_of_U-175_2.jpg Bletchley Park http://en.wikipedia.org/wiki/File:Bletchley_Park.jpg main brain? Alan Turing
(1912-1954) Did they give him a
big shiny medal
after the war? http://en.wikipedia.org/wiki/Alan_Turing http://en.wikipedia.org/wiki/File:Apple_Computer_Logo_rainbow.svg The End ZzZzZ Time Complexity Example: Sorting numbers 7 9 4 2 8 pick the first number and compare it with the others
remember the smallest number
switch places if it's smaller 2 9 4 7 8 2 4 9 7 8 and so on 2 4 7 9 8 2 4 7 8 9 how long did it take? it depends on the computer so don't measure the time just count the most common operation the most common
operation was: comparing two numbers 7 9 4 2 8
2 9 4 7 8
2 4 9 7 8
2 4 7 9 8
2 4 7 8 9 number of comparisons 4
0 Let be the number of operations when the input is of size when is large for some number is P is the set of all problems
that can be solved in polynomial time in time the exact definition
is about decision problems only
and uses a... It is possible to invent a single machine which can be used to compute any computable sequence. Turing, 1936 ...a deterministic Turing machine 0 0 0 0 1 1 1 1 1 1 NP is the set of all problems
that can be solved in polynomial time by a ... non-deterministic Turing machine Non-deterministic Polynomial NP is the set of all problems whose
solution can be another way of putting it: in polynomial time verified an example Problem: Given a graph with n vertices,
is there a Hamiltonian cycle? easy to verify a Hamiltonian cycle
does not exist the Hamiltonian-Cycle-problem is
solvable Brute Force: generate all permutations of the vertices and then... check them all! as far as anyone knows
there is no polynomial
time algorithm if you find one then P=NP another NP-hard problem is
factorizing into primes he wants to know if only he knew and he could find the secret key factorize ...all he has to do now is... into primes 100 digits primes he starts trying
but since... he's still trying if you prove it's false
the security of all computers... clearly but presumably... Want to prove
it's not?
Good luck! Eve Adam from big deal
computers get faster suppose Eve can make one operation in 1 Adam comes along and is 100 times faster suppose the input n is 100 take two problems #1 in P #2 in NP not very large takes takes 1 s 0.01 s 100 times faster 10 years 10 years 16 14 so make Adam faster a distance within an atom is the speed of light is 10 m 10 m -10 8 if and then a lower bound make Adam 10 times faster 14 impossible now takes 1 year ...make n slighlty larger
from 100 to 130 now takes 10 years 9 9 10 years old factorial time algorithms
take even longer could a problem
take longer time? Turing's Halting Problem Given a description of a program and a finite input,
decide whether the program finishes running or will
run forever, given that input. not solvable in finite time Proof compare to http://en.wikipedia.org/wiki/Kurt_G%C3%B6del Assume there is a program Halt such that: Halt(P,i) program input if P(i) ends in finite time return 'yes' else return 'no' Consider the program HaltYourself HaltYourself(P) return Halt(P,P) Consider the program Trouble(P) Trouble if HaltYourself(P) returns 'no' return 'yes' else infinite loop Now run the program Trouble on itself Trouble(Trouble) Will it halt? Contradiction!
The program fails Halt in 1952 Turing was prosecuted for homosexuality to escape prison he had to undergo chemical castration his security clearance was removed and he could
not continue working with cryptography in 1954 he was found dead in his bed the cause of death was cyanid poisoning beside his bed was a half-eaten apple 2009 August September http://news.bbc.co.uk/2/hi/8249792.stm http://news.bbc.co.uk/2/hi/technology/8226509.stm
Full transcript