PowerPoint Presentation
COSC1107 Computing Theory
(We will commence soon. We are just allowing a few minutes for people to join and set up. Please mute your microphone unless you are speaking.
You can raise your hand or use the chat at any time.)
1
This cover slide full of examples of structures.
Colour field to the right is discretised into cells we can identify by row and column.
Need precision and agreed conventions to speak about cells in our algorithms and for making sense of the data values – here colour values held by cells.
For example is cell indexed by 12 (x-axis) and 11 (y-axis) a blue colour value or not?
Test it! Discrete Structures are not ‘Being’ but ‘Doing’.
Well: are we starting to count from 0, or 1? Are we counting from the left top or left bottom or any other way?
Look at the graph to the left. Graphs are central to many algorithms and models. And this course will get to graphs in more detail. Let’s say this is a model of evidence collected in a investigation. Vertices might represent persons of interest, edges strong evidence of communication between them in the last couple of months. A key investigative question might be, “has the person of interest communicated with the victim?” According to the evidence?
Test it! P top left, V bottom right, say.
How do we prove this claim?
COSC1107
Computing Theory
Analysing Complexity
Week 10
Week 10
Computing Theory
james. .au
* With thanks to
Intro music ‘Far Over’ playing now …
2
This cover slide full of examples of structures.
Colour field to the right is discretised into cells we can identify by row and column.
Need precision and agreed conventions to speak about cells in our algorithms and for making sense of the data values – here colour values held by cells.
For example is cell indexed by 12 (x-axis) and 11 (y-axis) a blue colour value or not?
Test it! Discrete Structures are not ‘Being’ but ‘Doing’.
Well: are we starting to count from 0, or 1? Are we counting from the left top or left bottom or any other way?
Look at the graph to the left. Graphs are central to many algorithms and models. And this course will get to graphs in more detail. Let’s say this is a model of evidence collected in a investigation. Vertices might represent persons of interest, edges strong evidence of communication between them in the last couple of months. A key investigative question might be, “has the person of interest communicated with the victim?” According to the evidence?
Test it! P top left, V bottom right, say.
How do we prove this claim?
Acknowledgement
Week 10
Computing Theory
RMIT University acknowledges the people of the Woi wurrung and Boon wurrung language groups of the eastern Kulin Nations on whose unceded lands we conduct the business of the University. RMIT University respectfully acknowledges their Ancestors and Elders, past and present.
RMIT also acknowledges the Traditional Custodians and their Ancestors of the lands and waters across Australia where we conduct our business.
(add your name here to volunteer for this or email me)
(my personal Acknowledgement of Country is here)
3
Overview
Questions?
NP-completeness
Questions?
RSA Cryptosystem
Questions?
Probabilistic algorithms
Questions?
Platypus Game
Questions?
Week 10
Computing Theory
Of course!
4
Questions?
Questions?
Questions?
Week 10
Computing Theory
5
Complexity
Computing Theory
Week 10
LOGTIME
NP
EXPSPACE
Turing machines
P
PSPACE
EXPTIME
??
??
Our main focus
6
Complexity
Computing Theory
Week 10
NP
P
Finding a solution is easy
Checking a solution is easy;
Finding a solution is hard.
Checking a solution is hard
7
Complexity
Computing Theory
Week 10
NP
P
Finding a solution is easy
Checking a solution is easy;
Finding a solution is hard.
3SAT
HC
TSP
Primality, sorting, …
…
“Nobody is certain that P and NP are different, but many experts believe so …”
8
P = NP?
Computing Theory
Week 10
Clearly P NP. Is NP P? No proof either way!
Clay Institute in USA will give US$1 million to anyone who can settle this question!
Same prize for 6 other problems
First offered in 2000, only one has been claimed
See http://www.claymath.org/millennium-problems and
http://www.claymath.org/millennium-problems/p-vs-np-problem
How could you prove P = NP?
Find a polynomial-time algorithm on a (deterministic) TM for an NP-complete problem
How could you prove P NP?
Reason about all possible algorithms? (!!)
Neither has been done so far …
9
P = NP?
Computing Theory
Week 10
Many sub-classes of NP and PSPACE
No need to know all of these!
All could be empty if P = NP
10
Questions?
Questions?
Questions?
Week 10
Computing Theory
11
NP-completeness
Computing Theory
Week 10
A problem R is NP-complete if
R is in NP
If a polynomial-time algorithm exists for R, then a polynomial-time algorithm exists for every problem in NP
3SAT is NP-complete (!!!)
( , 1971. 1972. 1973. Cook & Karp won Turing Awards for this work)
NP-complete
“hardest” problems in NP
solve one and you solve them all …
2SAT is in P (!!)
12
Complexity
Computing Theory
Week 10
NP
P
3SAT
HC
TSP
NP-complete
2SAT
SORTING
PRIMALITY
13
NP-completeness
Computing Theory
Week 10
3SAT is NP-complete, i.e.
3SAT is in NP
If a polynomial-time algorithm exists for 3SAT, then a polynomial-time algorithm exists for every problem in NP
T
w
T(w)
R(w)
polynomial steps
deterministic
deterministic
3SAT
polynomial steps
w is an input for some problem R in NP
Assumed polynomial-time algorithm for 3SAT
Polynomial-time reduction of R to 3SAT
14
NP-completeness
Computing Theory
Week 10
3SAT is NP-complete
Hamiltonian Circuit is NP-complete
Travelling Salesperson is NP-complete
Vertex Cover is NP-complete
… is NP-complete ()
Thousands of problems are NP-complete (!!!)
(reduce 3SAT to your favourite problem in NP, and … )
15
NP-completeness
Computing Theory
Week 10
Reduce problem A to problem B means
You can solve A quickly if you can solve B quickly
You can solve A in polynomial time if you can solve B in polynomial time
B is at least as hard as A
A is no harder than B
A problem R is NP-hard if every problem in NP can be reduced to it in polynomial time
A problem R is NP-complete if it is both NP-hard and in NP
A problem can be NP-hard, but not NP-complete (so it is not in NP, as it is “too hard” for NP)
16
Complexity
Computing Theory
Week 10
NP
P
3SAT
HC
TSP
NP-complete
NP-hard
NP-hard: lower bound
“at least as hard as anything in NP, or perhaps harder”
In NP: upper bound
“No harder than checking solutions in polynomial time”
17
NP-completeness
Computing Theory
Week 10
Given new problem X, how do I analyse it?
Show that X is in NP (usually easy)
Find some NP-complete problem Y
Find a polynomial-time reduction from Y to X
Y
X
polynomial time
R
polynomial time
Any problem R in NP
Known NP-complete
problem
New problem
Already known
New part
18
NP-completeness
Computing Theory
Week 10
Aerospace engineering Optimal mesh partitioning for finite elements.
Biology Phylogeny reconstruction.
Chemical engineering Heat exchanger network synthesis.
Chemistry Protein folding.
Civil engineering Equilibrium of urban traffic flow.
Economics Computation of arbitrage in financial markets with friction.
Electrical engineering VLSI layout.
Environmental engineering Optimal placement of contaminant sensors.
Financial engineering Minimum risk portfolio of given return.
Game theory Nash equilibrium that maximizes social welfare.
Mechanical engineering Structure of turbulence in sheared flows.
Medicine Reconstructing 3D shape from biplane angiocardiogram.
Operations research Traveling salesperson problem, integer programming.
Physics Partition function of 3D Ising model.
Politics Shapley-Shubik voting power.
…
19
NP-completeness
Computing Theory
Week 10
https://complexityzoo.uwaterloo.ca/Complexity_Zoo
20
NP-completeness
Computing Theory
Week 10
“What is the state of the art for NP-complete problems?”
“Exponential-time algorithms” (!!)
“Surely we can do better than that?”
“Er … well, I wish …”
Even Gandalf doesn’t know
whether P = NP
whether there is a polynomial-time algorithm for some NP-complete problem
21
Questions?
Questions?
Questions?
Week 10
Computing Theory
22
Quiz time!
Week 10
Computing Theory
Go to Canvas and find the quiz Lectorial 10 Question set
Not worth any marks
You can consult other students if you wish
Time limit will be 5 minutes
Are you ready?
Are you sure?
23
Go!
The pictures will take 5 minutes to disappear!
Thomas music means 1 minute left!
Computing Theory
24
Questions?
Questions?
Questions?
Week 10
Computing Theory
25
NP-completeness
Computing Theory
Week 10
NP-complete problem
Find an efficient algorithm (and prove P = NP) (good luck!)
Approximation Find a sub-optimal solution efficiently
Heuristic Algorithm which “generally” works well, but doesn’t always work efficiently
Special case Use particular information to improve performance
Probabilistic Return an answer which is only probably correct
Randomised Use randomised search to find something quickly
26
NP-completeness
Computing Theory
Week 10
We cannot find an algorithm which
Runs in polynomial time for all inputs
Finds an optimal solution for all inputs
So any algorithm must
Runs in exponential time for some inputs
Finds a sub-optimal solution for some inputs
Both (!!)
27
Approximation
Computing Theory
Week 10
TSP
One approximation O(n2) with solution ≤ 2 x optimum
One approximation O(n3) with solution ≤ 1.5 x optimum
Runs in polynomial time for all inputs
Finds a sub-optimal solution
Guaranteed to be efficient
Not guaranteed to be optimal
28
Heuristic
Computing Theory
Week 10
TSP
Lin-Kernighan heuristic: swaps pairs of sub-tours
Greedy: choose shortest next
Inserting sub-tours
…
Some inputs take exponential time
“Common” or “typical” inputs take polynomial time
Often use local improvements
Few guarantees
29
Special case
Computing Theory
Week 10
HORN-SAT: SAT with at most one positive literal per clause
(p q r ) (r q w) (p p r )
Extra information used to improve performance
Polynomial time for some special cases
Approximations for some special cases
A
B
C
TSP with Euclidean distance:
|AC| ≤ |AB| + |BC|
Improved approximation
Polynomial time
30
Week 10
Computing Theory
Encryption
Intractability can be your friend!
Encryption historically based on secret keys
Caesar cipher, Playfair cipher, Enigma
Substitution and transposition
Advanced Encryption Standard (AES)
Secret key systems have the key distribution problem
Question: How do you communicate a secret key securely?
Answer: With great difficulty!
31
Week 10
Computing Theory
Encryption
Mr Worf! Open a secure channel to Starfleet!
Yes Captain! How do I do that?
Send them our encryption key and get them to
use that!
On an open channel? That sounds like a security risk …
Of course! Open a secure channel, Mr Worf!
32
Week 10
Computing Theory
Encryption
Asymmetric approaches were a major breakthrough!
Diffie-Hellman key exchange (1976)
First scheme to have separate encryption and decryption keys
Proposed by and , and also
RSA Public key cryptosystem (1977)
Encryption key is public, decryption key is private
Based on property of prime numbers (!!)
Security assumes factorisation is intractable
Proposed by , &
Other public key systems use more advanced mathematics (discrete logarithms, elliptic curves, finite groups, …)
British GCHQ announced in 1990s that they knew this in 1969 …
33
Factorisation
Computing Theory
Week 10
Factorisation
‘Find factors of n’
Intuitively harder than primality testing
Can use factorisation for primality testing but not recommended
NOT NP-complete!
Almost certainly intractable …
Shor’s algorithm is tractable for factorisation on a quantum computer
Blockchain
Public Key Cryptography
RSA System
Intractability of Factorisation
34
Intractability
Computing Theory
Week 10
Can be your friend!
INTRACTABILITY
Blockchain, SSH, ecommerce, encryption, security …
Public Key Cryptography
RSA
Intractability
Discrete Logarithms
Elliptic Curves
Quantum Computing
35
Week 10
Computing Theory
Encryption
“new password
is bumblebee”
“new password
is bumblebee”
Send
Decrypt
Encrypt
xsgfhasfgedg
xsgfhasfgedg
Public (so anyone can encrypt)
Private (so only Bob can decrypt)
36
RSA System
Computing Theory
Week 10
Public Key cryptography
Two keys, E for encryption and D for decryption
Publish E
Keep D secret
Knowledge of E must not imply knowledge of D
Hence make computing D from E intractable
This means we need to make E “large enough”
RSA scheme (Rivest, Shamir, Adleman 1977)
Find two primes p and q
Compute n = p x q and r = (p-1) x (q-1)
Find e such that e and (p-1) x (q-1) are co-prime
Compute d such that d x e 1 mod r
Encrypt M by E(m) = me mod n
Decrypt M by D(m) = md mod n
D(E(m)) = me x d m mod n
E published
D kept secret
Secure if computing D from E is intractable
To find d from e and n, need to know p & q (and hence r)
Uses (extended) Euclid’s algorithm (!!)
e,n public
“Find 3 primes p, q, e” will work
37
Cracking RSA
Computing Theory
Week 10
RSA scheme
Find two primes p and q
Compute n = p x q and r = (p-1) x (q-1)
Find e such that e and (p-1) x (q-1) are co-prime
Compute d such that d x e 1 mod r
Public: e, n
Private: d, p, q, r
Process Method Complexity
Calculate d from e and r Euclid’s algorithm Quadratic
Calculate r from p and q Multiplication Close to constant
Calculate p and q from n Number field sieve INTRACTABLE
Factorisation
Almost certainly intractable
Not obvious that it is harder than primality testing
Input n has representation size log n
Polynomial time in the size of the input means O(log n) (!!)
(d x e) + (z x r) = 1 = gcd(e,r)
38
Setting up RSA
Computing Theory
Week 10
Need to find primes quickly!
Primality testing
Decision problem
Long unknown whether polynomial or not
Miller in 1976 showed there is a polynomial algorithm assuming the Extended Riemann Hypothesis is true
Agrawal, Kayal, Saxena found polynomial-time algorithm in 2002 (!!)
Kayal, Saxena were undergraduate students at the time (!!!)
Little pragmatic impact because …
Probabilistic methods are much faster (!!)
RSA scheme
Find two primes p and q
Compute n = p x q and r = (p-1) x (q-1)
Find e such that e and (p-1) x (q-1) are co-prime
Compute d such that d x e 1 mod r
Public: e, n
Private: d, p, q, r
39
Questions?
Questions?
Questions?
Week 10
Computing Theory
40
Week 10
Computing Theory
‘Marvellous Machine’
41
Week 10
Computing Theory
`Marvellous Machine’
“Counts grains of sand exactly within one second”
“4,292,303,203,201,204 grains of sand”
??????
“Yeah? Well count this!
42
Week 10
Computing Theory
`Marvellous Machine’
“4,292,303,203,201,204”
“4,292,303,203,201,209”
+5
“4,292,303,203,201,192”
-12
“4,292,303,203,201,218”
+14
“4,292,303,203,201,197”
-7
43
Week 10
Computing Theory
`Marvellous Machine’
Machine has to pass numerous trials
Failure at any time means machine fails acceptance test
Trial 1 successful: Lucky guess!
Trial 2 successful: Still just luck
Trial 3 successful: Hmm…
Trial 4 successful: ???
Trial 5 fails: GOTCHA!
44
Week 10
Computing Theory
`Marvellous Machine’
Trial 1 successful: Lucky guess!
Trial 2 successful: Still just luck
Trial 3 successful: Hmm…
Trial 4 successful: ???
Trial 5 successful: So what’s the trick?
Trial 6 successful: Really — what is it?
Trial 7 successful: Now this is just getting boring …
…
Trial 47 successful: Alright! You win! It works!
45
Probabilistic Algorithms
Computing Theory
Week 10
“Approximation method” for decision problems …
Series of tests is applied
If any test fails, the answer is ‘no’
Each successful test is ‘evidence’ for ‘yes’
More successful tests means more likelihood of ‘yes’
Can either return
No (with certainty)
Probably yes (usually with a specific probability)
Less precision but much more efficient
46
Week 10
Computing Theory
Primality Testing
Given a number n
Choose k such that 1 < k < n
If n mod k = 0, halt with output ‘no’
If enough trials done then halt ‘probably yes’
Go to step 1.
How to choose k?
k = 2, 3, 5, 7, … n/2(or n) gives sieve of Eratosthenes (exponential)
Smarter choice means less cases to test
47
Week 10
Computing Theory
Probabilistic Primality Testing
Testing for a strict subset of {2,3,5,7,..., n} can only ever give the result `probably prime'
Trick is to make `good' choices of k
Solovay-Strassen test:
correctness probability after m trials is 1 – 1/2m (!)
Rabin-Miller test:
correctness probability after m trials is 1 – 1/4m (!!)
Can have arbitrarily high correctness if we perform enough trials ....
48
RSA Pragmatics
Computing Theory
Week 10
Primality testing
AKS algorithm says yes or no in polynomial time
Solovay-Strassen test says probably yes or definitely no in much shorter time!
Rabin-Miller test says probably yes or definitely no in much shorter time still!
The trick is to increase the probability of correctness to almost 1 after a smallish number of steps …
n SS(n) RM(n)
1 50% 75%
2 75% 94%
5 97% 99.9%
10 99.9% 99.9999%
25 99.999997% 99.999999999999%
Any size number can be tested for primality in about 25 trials … (!!)
49
Week 10
Computing Theory
RSA Properties
Can be used for any encryption task
Encryption and decryption speeds slow compared to secret key methods (eg AES)
Often used to distribute secret keys
Used in SSH and similar tools
Security depends on the size of the primes used
1024 to 4096 bits recommended, 2048 considered ‘safe’
Threats
Factorisation being tractable
Quantum computing (using Shor’s algorithm)
Other public-key systems with shorter keys and more efficient encryption
…
50
The Platypus Game
Week 10
Computing Theory
https://www.youtube.com/watch?reload=9&v=0gM5TjSOQ48
https://zoneringtones.com
51
Assignment 2
Week 10
Computing Theory
Platypus tournament for 2,500 machines
Earlier distribution had 25,500 (in error)
If 2,500 machines takes more than 4 hours, reduce the number (to say 2,000)
Three tournaments to be run:
All 2,500 machines
Only machines classified as ‘reachable’
Only machines classified as ‘none’ or ‘unreachable’
Pointers on intractability question will be posted soon
52
That’s it!
Week 10
Computing Theory
I am out of here!
53
Break time! (We resume when all the pictures are gone! This will take 3 minutes!)
Computing Theory
54
Quiz time!
Week 10
Computing Theory
Go to Canvas and find the quiz Lectorial 10 Question set
Not worth any marks
You can consult other students if you wish
Time limit will be 10 minutes
Are you ready?
Are you sure?
55
Go!
The pictures will take 10 minutes to disappear!
Thomas music means 1 minute left!
Computing Theory
56
LOG
Time
LOG
Space
PTIME
N
P
T
IM
E
NPC
co
-N
P
T
IM
E
PSPACE
EXPTIME
EXPSPACE
...
ELEMENTARY
...
2EXPTIME
RECURSIVE
1
null
30067.158
ppPlatypus Song Ringtone 1 (P-P-P)
ppPlatypus Song Ringtone 1 (P-P-P)
/ Axtell Entertainment
null, track 1
© 2010
Humour
16927.266
��� -
For Private Use - Other use contact www.axtell.com