PowerPoint Presentation
COSC1107 Computing Theory
Copyright By PowCoder代写加微信 assignmentchef
(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.)
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?
Computing Theory
Analysing Complexity
Computing Theory
* With thanks to
Intro music ‘Far Over’ playing now …
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
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)
Questions?
NP-completeness
Questions?
RSA Cryptosystem
Questions?
Probabilistic algorithms
Questions?
Platypus Game
Questions?
Computing Theory
Of course!
Questions?
Questions?
Questions?
Computing Theory
Complexity
Computing Theory
Turing machines
Our main focus
Complexity
Computing Theory
Finding a solution is easy
Checking a solution is easy;
Finding a solution is hard.
Checking a solution is hard
Complexity
Computing Theory
Finding a solution is easy
Checking a solution is easy;
Finding a solution is hard.
Primality, sorting, …
“Nobody is certain that P and NP are different, but many experts believe so …”
Computing Theory
Clearly PNP. Is NPP? 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-problemsand
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 PNP?
Reason about all possible algorithms? (!!)
Neither has been done so far …
Computing Theory
Many sub-classes of NP and PSPACE
No need to know all of these!
All could be empty if P = NP
Questions?
Questions?
Questions?
Computing Theory
NP-completeness
Computing Theory
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 (!!)
Complexity
Computing Theory
NP-complete
NP-completeness
Computing Theory
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
polynomial steps
deterministic
deterministic
polynomial steps
w is an input for some problem R in NP
Assumed polynomial-time algorithm for 3SAT
Polynomial-time reduction of R to3SAT
NP-completeness
Computing Theory
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 … )
NP-completeness
Computing Theory
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)
Complexity
Computing Theory
NP-complete
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”
NP-completeness
Computing Theory
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
polynomial time
polynomial time
Any problem R in NP
Known NP-complete
New problem
Already known
NP-completeness
Computing Theory
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.
NP-completeness
Computing Theory
https://complexityzoo.uwaterloo.ca/Complexity_Zoo
NP-completeness
Computing Theory
“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
Questions?
Questions?
Questions?
Computing Theory
Quiz time!
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?
The pictures will take 5 minutes to disappear!
Thomas music means 1 minute left!
Computing Theory
Questions?
Questions?
Questions?
Computing Theory
NP-completeness
Computing Theory
NP-complete problem
Find an efficient algorithm (and prove P = NP) (good luck!)
ApproximationFind a sub-optimal solution efficiently
HeuristicAlgorithm which “generally” works well, but doesn’t always work efficiently
Special case Use particular information to improve performance
ProbabilisticReturn an answer which is only probably correct
RandomisedUse randomised search to find something quickly
NP-completeness
Computing Theory
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
Approximation
Computing Theory
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
Computing Theory
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
Special case
Computing Theory
HORN-SAT: SAT with at most one positive literal per clause
(p q r )(rqw)(pp r )
Extra information used to improve performance
Polynomial time for some special cases
Approximations for some special cases
TSP with Euclidean distance:
|AC|≤ |AB| + |BC|
Improved approximation
Polynomial time
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!
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
On an open channel? That sounds like a security risk …
Of course! Open a secure channel, Mr Worf!
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 …
Factorisation
Computing Theory
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
Intractability
Computing Theory
Can be your friend!
INTRACTABILITY
Blockchain, SSH, ecommerce, encryption, security …
Public Key Cryptography
Intractability
Discrete Logarithms
Elliptic Curves
Quantum Computing
Computing Theory
Encryption
“new password
is bumblebee”
“new password
is bumblebee”
xsgfhasfgedg
xsgfhasfgedg
Public (so anyone can encrypt)
Private (so only Bob can decrypt)
RSA System
Computing Theory
Public Key cryptography
Two keys, E for encryption and D for decryption
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 thatd x e1 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
Cracking RSA
Computing Theory
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 thatd x e1 mod r
Public: e, n
Private: d, p, q, r
ProcessMethodComplexity
Calculate d from e and r Euclid’s algorithmQuadratic
Calculate r from p and q MultiplicationClose to constant
Calculate p and q from n Number field sieveINTRACTABLE
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)
Setting up RSA
Computing Theory
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 thatd x e1 mod r
Public: e, n
Private: d, p, q, r
Questions?
Questions?
Questions?
Computing Theory
Computing Theory
‘Marvellous Machine’
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!
Computing Theory
`Marvellous Machine’
“4,292,303,203,201,204”
“4,292,303,203,201,209”
“4,292,303,203,201,192”
“4,292,303,203,201,218”
“4,292,303,203,201,197”
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!
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!
Probabilistic Algorithms
Computing Theory
“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
Computing Theory
Primality Testing
Given a number n
Choose k such that 1 < k < nIf 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 Computing TheoryProbabilistic Primality TestingTesting 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 kSolovay-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 ….RSA PragmaticsComputing TheoryPrimality testing AKS algorithm says yes or no in polynomial timeSolovay-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 … nSS(n)RM(n)597%99.9%1099.9%99.9999%2599.999997%99.999999999999%Any size number can be tested for primality in about 25 trials … (!!)Computing TheoryRSA PropertiesCan be used for any encryption taskEncryption 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 used1024 to 4096 bits recommended, 2048 considered ‘safe’Factorisation being tractableQuantum computing (using Shor’s algorithm)Other public-key systems with shorter keys and more efficient encryption The Platypus GameComputing Theoryhttps://www.youtube.com/watch?reload=9&v=0gM5TjSOQ48https://zoneringtones.com Assignment 2Computing TheoryPlatypus tournament for 2,500 machinesEarlier 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 machinesOnly machines classified as ‘reachable’Only machines classified as ‘none’ or ‘unreachable’Pointers on intractability question will be posted soonThat’s it!Computing TheoryI am out of here!Break time! (We resume when all the pictures are gone! This will take 3 minutes!)Computing TheoryQuiz time!Computing TheoryGo to Canvas and find the quiz Lectorial 10 Question setNot worth any marksYou can consult other students if you wishTime limit will be 10 minutesAre you ready?Are you sure?The pictures will take 10 minutes to disappear! Thomas music means 1 minute left!Computing TheoryELEMENTARYppPlatypus Song Ringtone 1 (P-P-P)ppPlatypus Song Ringtone 1 (P-P-P)/ Axtell Entertainmentnull, track 1For Private Use – Other use contact www.axtell.com程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.