### Present Remotely

Send the link below via email or IM

CopyPresent 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

# P vs NP

No description

by

Tweet## Malin Christersson

on 25 March 2011#### 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

3

2

1

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 transcripthe 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

3

2

1

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