04-07-2012, 02:20 PM
P versus NP and Cryptography
p-versus-np.ppt (Size: 824 KB / Downloads: 94)
NP, more examples
Is a math claim true
“Easy” to check the proof
Routing/Scheduling
Nash Equilibria in some settings
DNA/protein matching
Graph problems (vertex cover, clique, TSP, …)
Knapsack, subset sum, bin packing …
Integer programming
…
P versus NP and cryptography
Cryptography
“One way” function (e.g., multiplication)
If P=NP
No one way functions! No cryptography!
If P not equal to NP
Not known to imply one way functions
(showing that would be major result.)
Hard to even approximate many scheduling/routing/etc. problems
(Major breakthrough in the 90’s)
Better than brute force
Is a given number prime?
Linear programming
Simple example: shortest path
Remember wherewe have been already!