COSC1107/1105 Computing Theory
School of Computing Technologies Semester 2, 2021
Tutorial No. 6: Undecidability and Complexity
The aim of this tutorial is to investigate the reduction technique and the complexity of algorithms. You will develop some proofs for showing undecidability of problems and gain experience with the use of O(n) notation. The most important parts are parts 1, 2 and 3.
Before this tutorial you are expected to have read Section 1 of the Computing Theory notes. It is also assumed that you completed the section “Comparing Complexity” in Tutorial 1.
Before you begin:
Many (if not all) of the undecidability and Big-O questions in this tutorial sheet can be solved using proof by contradiction. Recall, that in order to prove a proposition P , by contradiction, you must:
• State the proposition you intend to prove (P ), and that you are doing so via contradiction;
• Assume the proposition you want to prove is FALSE (i.e, ¬P is TRUE);
• Use this assumption to derive a result that contradicts a known fact (e.g., the halting problem is undecidable); and, • Conclude that your assumption must be incorrect (i.e., ¬P is FALSE) and the proposition P is in fact TRUE. QED.
Keep these points in mind, as you work through the questions in parts 2 and 3.
PART1: HaltingTuringMachines……………………………………………………………….
Consider the Turing machine M1 below:
q0
(a) Complete the transition table for M1:
B/B,R
q1
q2 a/a,R
q3 b/b,R
δBab q0
q1
q2
q3
Solution:
δBab
q0 q1,B,R
q1 q2,a,R q2,b,L q3,a,L q2 q1,b,L q2,a,R q3,a,R q3 q1,a,L q2,b,R q3,b,R
1
B/a,R a/b, L
B/b,L
b/a,R
a/b, R
B/a,L b/a, L
COSC1107/1105 – Computing Theory Tutorial 6: Undecidability and Complexity Page 2 of 9 (b) If the initial configuration for M1 is q0,BuB for some input string u ∈ Σ∗. Referring to your answer to part (a),
explain why M1 will never halt.
(c) Disregarding the initial configuration above, referring again to your answer to part (a), under which circumstances would this machine halt?
PART2: ShowingUndecidability………………………………………………………………… The following example illustrates a concept that is very important when constructing undecidability proofs.
Turing machine M1 takes one of the three following inputs B1×1B, B1+1B or B1−1B and completes its computation by leaving 1, 2 or 0 on a blank tape — effectively computing the answers to 1 × 1, 1 + 1 and 1 − 1.
q3 q0 B/B,R
q6 q4 q2 q1
Solution:
A Turing machine will halt when it encounters an input in a state for which it has no transition. As the input configuration for M1 is q0, BuB, it will never encounter any other input than a blank while in q0, and the transition table is complete for every other state, meaning that no matter what input the machine recieves, it will always have something it can do.
Solution:
M1 will halt with either of the following input configurations q0, auB or q0, buB, for some u ∈ Σ∗, as these are the only missing entries in the transition table.
q5
Turing machine M2 takes any input of the form BuB where u ∈ Σ∗ and erases anything that was previously written on its tape and replaces it with B1 + 1B, before returning to the start of the input.
∀x∈Σ x/x,R ∀x∈Σ x/B,L B/B, L
B/B, R
q0 q1 q2
M2
∀x ∈ {1,+} x/x,L
M1
1/1, L
×/B, R 1/B, R
B/B,R
B/1, L B/+, R B/1, R
q6 q5 q4 q3
By combining M1 and M2 into a machine M3, we can construct a machine that will always compute the answer to 1 + 1, regardless of what is put into it to begin with.
RMIT CT 2021 (Semester 2) – Exercise 2 continues on the next page. . .
1/2, L
−/B,R
+/B,R
1/0, L
COSC1107/1105 – Computing Theory
Tutorial 6: Undecidability and Complexity
Page 3 of 9
q9
B/B, R
M3 q0
∀x ∈ {1,+} x/x,L
∀x∈Σ x/x,R q1
B/B, L
∀x∈Σ x/B,L q2
B/B,R
B/1, R
q12 q10 q8 q7 q6 q5 q4 q3
B/1, L
B/+, R
1/1, L
×/B, R 1/B, R B/B, R
q11
Now, regardless of whatever input is given to it, M3 will always simulate the operation of M1 on input B1 + 1B. We can
demonstrate this with a trace of M3 on input B1 × 1B: q0,B1×1B⊢
q1,B1×1B⊢
.
q1,B1×1B⊢ q2,B1×1B⊢ q2,B1×BB⊢ q2,B1BBB⊢ q2,BBBBB⊢ q3,BBBBB⊢
…
q4,B1BBB⊢ q5,B1+BB⊢
q6,B1+1B⊢ q6,B1+1B⊢ q6,B1+1B⊢ q7,B1+1B⊢ q8,BB+1B⊢ q9,BBB1B⊢ q12, BBB2B ⊢
Here you can see that M3 will always terminate with a 2 on an otherwise empty tape, even if its input is B11111B, an otherwise invalid input!
This is an important result, as with many undecidability proofs it is useful to be able to simulate the operation of some machine M on some given input w, regardless of the input that is given to M. To do this, we can create a new machine Mw that deletes whatever is on the tape and writes w before beginning its computations — effectively simulating M on input w, irrespective of what is originally passed to Mw.
Questions:
Show that the following problems are undecidable:
(a) Determine whether a Turing machine M halts on all inputs.
Solution:
Suppose there does exist a machine X which is able to decide whether M halts on all inputs. Let us build a Turing machine H, that takes a machine M and an input w, as follows:
• First, machine H takes M and builds from it an alternative Turing machine M w as follows: M w deletes the tape and writes w on it, and then operates like M (on the string w that was just written).
• Second, machine H runs X on Mw.
We next show that H solve the Halting Problem::
• Suppose that M halts on input w. Then, Mw will halt on any input, because it effectively is just deleting it and then running M on w, which halts. Hence, X will accept on input Mw, and so will H on M and w.
• Suppose that M runs forever on input w. Then Mw will run forever on any input, as it effectively runs M on w anyways. So, X will reject and so will H, as expected.
This means that H solves the Halting Problem, a contradiction. Hence, X cannot exist and the problem is undecid- able.
(b) Determine whether a Turing machine M halts on some input (i.e., there does exist at least one input for which M halts, we just don’t know it).
RMIT CT 2021 (Semester 2) –
1/2, L
−/B,R
+/B,R
1/0, L
COSC1107/1105 – Computing Theory Tutorial 6: Undecidability and Complexity Page 4 of 9
Solution:
Same proof as for all inputs should work. Why? If Mw is just simulating the operation of M on w, then if M halts on w, Mw will halt for every input. Hence, there will, trivially, be at least one input for which M halts.
Also one can reduce HALTEMPTY by transforming M to M ′ where M ′ deletes everything from the tape and then runs like M.
(c) Determine whether or not a Turing machine M when run on input w will ever reach a state q of M .
Solution: Suppose there does exist a machine X which is able to solve such problem. That is X receives M, w and q and decides whether M will ever reach state q when run on input w.
Let us build a Turing machine H as follows:
• First, machine H takes M and builds from it an alternative Turing machine Y as follows: Y operates exactly like M , but whenever a transition is not defined in M (and hence, M would halt), the machine Y transitions to a new state q not mentioned in M (that is Y has q but M has no state named q) and halts (no transition is defined for state q).
• After that, machine H runs X on Y , w, and q, and returns X’s output.
We next show that our TM H that we just build (using X) solves the Halting Problem:
• Suppose that M halts on input w. Then Y , when ran on w, will first execute like M and then transition to stateq;soY reachesqwhenranoninputw.So,XwillacceptwhenranoninputM,wandq,andsoHwill accept to (signaling that M halts as expected).
• Suppose that M runs forever on input w. This means that Y will also run forever on w and will never reach its state q (as Y can only reach q when M halts). Then X will reject when ran on Y, w, and q, and so will H, as wanted.
This means that H solves the Halting Problem, a contradiction. Hence, X cannot exist and the problem is undecid- able.
(d) Determine whether two Turing machines halt on exactly the same inputs.
Solution:
We reduce the Halting problem to this problem to show that it is undecidable. Suppose there does exist a Turing machine X that is able to decide if two arbitrary Turing machines M1 and M2 halt on exactly the same inputs.
Let us build a Turing machine H as follows:
• First machine H takes M and w and builds a machine Mw which simulates M being run on w. • Then H creates a second, dummy machine M′ which halts immediately.
• Finally, H runs X on Mw and M′ and accepts if X accepts.
We next show that H solves the Halting Problem:
• Suppose that M halts on input w. Then Mw will always halt, as does M′, so X will accept; which means
that H accepts also.
• Suppose that M runs forever on input w. Then, [. . . fill this part!. . . ]
This means that H solves the Halting Problem, a contradiction. Hence, X cannot exist and the problem is undecid- able.
(e) Determine whether a Turing machine M accepts an input w. We call that problem AT M .
Solution:
We reduce the Halting problem to this problem to show that it is undecidable. Suppose there does exist a Turing machine X that is able to decide if a given Turing machine accepts an given input.
Let us build a Turing machine H as follows:
• First, machine H takes M and builds a machine M ′ that is exactly like M except that it makes all the states final states. So M ′ either accepts or runs forever.
• Then H runs X on M′ and accepts if X accepts. We next show that H solves the Halting Problem:
• Suppose that M halts on input w. Then M′ will accept w. So, X will accept when run on M′ and w (as all states in M′ are now final), which means that H accepts too when run on M and w, as expected.
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 6: Undecidability and Complexity Page 5 of 9
• Suppose that M does not halt on input w (i.e., it will run forever). Then, M′ will run forever on w as well; and therefore X will reject when given M′ and w. Thus H itself will reject on M and w, as expected.
This means that H solves the Halting Problem, a contradiction. Hence, X cannot exist and the problem is undecid- able.
(f) Determine whether a Turing machine M is such that L(M ) = ∅.
Solution:
We reduce the Halting problem to this problem to show that it is undecidable. Suppose there does exist a Turing machine X that is able to decide if the language of a Turing machine is empty.
Let us build a Turing machine H as follows:
• First machine H takes M and builds a machine Mw that deletes its tape, writes w, and then simulates M on w. If M halts on w then Mw accepts.
• Then H runs X on Mw and accepts if X rejects. We next show that H solves the Halting Problem:
• Suppose that M halts on input w. Then Mw will always accept, so X will reject when run on Mw; which means that H accepts.
• Suppose that H does not halt on M and w. […fill this part!…].
This means that H solves the Halting Problem, a contradiction. Hence, X cannot exist and the problem is undecid- able.
(g) Using the undecidability of AT M , determine whether a Turing machine M is such that L(M ) is a regular language. Without loss of generality, assume Σ = {0, 1}.
Solution:
We are to reduce AT M to our problem. Suppose we do have a Turing machine X that solves the regular problem. Let us build a Turing machine H as follows:
• First of all, H builds a special Turing machine W which has one input x as follows:
– If x is of the form 0n1n, then W accepts. This means that L(0n1n) ⊆ L(W).
– If, on the other hand, x is not of the form 0n1n, then W simulates M on w, so it will accept x iff M
accepts w (otherwise will reject or run forever, as M does). • Second, H passes W to machine X
We can then show that H solves ATM, when given M on w:
• Suppose that M accepts w, that is, w ∈ L(M). Then L(W) = Σ∗ (i.e., W accepts all the strings). Why? if
W is ran on a word of the shape 0n1n, W will accept it; and if run on a word not of that shape, then W will run M on w which will accept too: so every word will be accepted by W when M accepts w. So, when W isgiventoX,X willacceptandsowillH onM andw.
• Suppose that M does not accept w (may reject or run forever on w), that is, w ̸∈ L(M). Then, W will only accept inputs of the form 0n1n (for any other input, M on w will be simulated, which does not accept). So, L(W) = L(0n1n) which is not regular, and hence X will reject, and so will H, as expected,
This means that H solves the AT M , which is not possible as per question before. Hence, X cannot exist and the problem is undecidable.
(h) Determine whether two Turing machines M1 and M2 are such that L(M1) = L(M2).
Solution:
We reduce the Halting problem to this problem to show that it is undecidable. Suppose there does exist a Turing machine X that is able to decide if L(M1) = L(M2), i.e., the languages of two arbitrary Turing machines M1 and M2 are the same.
Let us build a Turing machine H as follows:
• First machine H takes M and w and builds a machine Mw which simulates M being run on w and accepts if M halts.
• Then H creates a second, dummy machine M ′ which accepts everything.
• Finally, H runs X on Mw and M′ and accepts if X accepts. We next show that H solves the Halting Problem:
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 6: Undecidability and Complexity Page 6 of 9
• Suppose that M halts on input w. Then Mw always accepts, as does M′, so their languages are equivalent and X will accept; which means that H accepts also.
• Suppose that M does not halt on input w. Then, [. . . fill this part!. . . ].
This means that H solves the Halting Problem, a contradiction. Hence, X cannot exist and the problem is undecid- able.
PART3: ProofsonBig-O………………………………………………………………………… There are many ways to prove propositions around Big-O, two common ways (proof by contradiction and direct proof) are shown below in detailed, worked examples. These proofs use the following definitions:
Mathematical Definition of being a member of the the set O(g(n)):
f(n)∈O(g(n))⇔∃n0 ∈N, ∃c∈R+, ∀n∈N, n≥n0, f(n)≤c·g(n)
Mathematical Definition of not being a member of the the set O(g(n)):
Examples:
f(n) ∈/ O(g(n)) ⇔ ¬(f(n) ∈ O(g(n)))
⇔¬(∃n0 ∈N, ∃c∈R+, ∀n∈N, n≥n0, f(n)≤c·g(n))
⇔∀n0 ∈N, ∀c∈R+, ∃n∈N, n≥n0, f(n)>c·g(n)
(a) Prove that running time T (n) = n4 + 15n2 + 2 ∈ O(n4). We can do this by direct proof:
• State what you’re going to prove:
– We will prove that (n4 + 15n2 + 2) ∈ O(n4).
– I.e.∃n0 ∈N, ∃c∈R+, ∀n∈N,n≥n0,(n4 +15n2 +2)≤c·n4.
• Exploration (Show existence (∃) by identifying candidate values of n0 and c): – Notethat∀n∈N, n≥1,wehave
n4 +15n2 +2≤n4 +n2(15n2)+n4(2) = n4 +15n4 +2n4
= 18n4.
– Sochoosen0 =1,andc=18.
• Now show your choice of n0 and c satisfy the Big O definition:
– Letn∈N,suchthatn≥1.
– ThenT(n)=n4 +15n2 +2≤n4 +15n4 +2n4 ≤18n4. • Conclusion:
– HenceT(n)∈O(n4),withn0 =1,andc=18. – Q.E.D.
(b) Prove that running time T (n) = n4 + 15n2 + 2 ∈/ O(n3) We can do this by contradiction:
• State what you’re going to prove:
– We will prove that T(n) = n4 + 15n2 + 2 ∈/ O(n3) by contradiction.
• Assume the proposition you want to prove is FALSE.
– AssumeT(n)=n4 +15n2 +2∈O(n3).
– I.e.∃n0 ∈N, ∃c∈R+, ∀n∈N,n≥n0,(n4 +15n2 +2)≤c·n3.
• Derive a contradiction:
– Now consider n = n0 · ⌈c⌉, and note that n ∈ N, and n ≥ n0 (We can do this because our assumption tells
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 6: Undecidability and Complexity Page 7 of 9 us that n0 and c exist – we just don’t happen to know what they are). Then
c·n3 ≤⌈c⌉·n3
= ⌈c⌉(n0 · ⌈c⌉)3
= n 30 · ⌈ c ⌉ 4
≤ n 40 · ⌈ c ⌉ 4
< n40 ·⌈c⌉4 +15(n0 ·⌈c⌉)2 +2 =n4 +15n2 +2.
– Thatis,n4 +15n+2>c·n3,whenn=n0 ·⌈c⌉.
– Which contradicts our assumption. • Conclusion:
– Hence our assumption that T(n) = n4 + 15n2 + 2 ∈ O(n3) must be FALSE, and in fact T(n) = n4 + 15n2 + 2 ∈/ O(n3), as required.
– Q.E.D.
(c) ProvethatrunningtimeT(n)=n2 ·logn+11n+4∈O(n4). We can do this by direct proof:
• State what you’re going to prove:
– Wewillprovethat(n2 ·logn+11n+4)∈O(n4).
– I.e.∃n0 ∈N, ∃c∈R+, ∀n∈N,n≥n0,(n2 ·logn+11n+4)≤c·n4.
• Exploration (Show existence (∃) by identifying candidate values of n0 and c): – Notethat∀n∈N,logn≤n.Then,forn≥1wehave
n2 ·logn+11n+4≤n2 ·n+11n+4
≤ n(n3) + n3(11n) + n4(4)
= n4 +11n4 +4n4 = 16n4.
– Sochoosen0 =1,andc=16.
• Now show your choice of n0 and c satisfy the Big O definition:
– Letn∈N,suchthatn≥1.
– ThenT(n)=n2 ·logn+11n+4≤n4 +11n4 +4n4 ≤16n4. • Conclusion:
– HenceT(n)∈O(n4),withn0 =1,andc=16. – Q.E.D.
Keep in mind that different proof methods can be more complicated than others, for certain problems, when deciding how you are going to prove your propositions. Typically, direct proof will work better for proving T (n) ∈ O(g(n)) and contradiction will work better for proving T (n) ∈/ O(g(n)). These rules are not iron-clad, but decent rules-of-thumb.
(NB: These examples are structured in this way to make the proof techniques used as explicitly clear as possible, you do not need to include bullet points with “State what you’re going to prove:” in your solutions.)
Questions:
(a) Define formally what it means that f(n) ∈ O(g(n)) (i.e., function f(n) is said to be of order g(n)).
(b) Prove that running time T (n) = n3 + 20n + 1 ∈ O(n3).
Solution:
Function f(n) is said to be of order g(n) (i.e., f(n) ∈ O(g(n))) iff there is a positive constant c and a natural numbern0 suchthatf(n)≤c×g(n),foralln≥n0.
Observe that O(g(n)) is a set of functions.
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 6: Undecidability and Complexity Page 8 of 9
Solution:
Proof: We prove this by direct proof.
BythedefinitionofBig-O,T(n)∈O(n3)iffthereexistsan0 ∈N,ac∈R+ foralln∈Nwithn≥n0,suchthat n3 +20n+1≤c·n3.
Notethat∀n∈N,n≥1,wehaven3+20n+1≤n3+20n3+1n3 =22n3.Hence,T(n)≤c·n3,∀n≥n0, withc=22andn0 =1andT(n)∈O(n3).QED.
(c) Prove that running time T (n) = n3 + 20n + 1 ̸∈ O(n2).
Solution:
Proof: We prove this by contradiction.
AssumeT(n)∈O(n2). BythedefinitionofBig-Othereexistsan0 ∈N,ac∈R+ foralln∈Nwithn≥n0, suchthatn3 +20n+1≤c·n2.
Now, consider n = n0 · ⌈c⌉. Then
c·n2 ≤⌈c⌉·n2
= ⌈c⌉(n0 · ⌈c⌉)2
= n 20 · ⌈ c ⌉ 3
≤ n 30 · ⌈ c ⌉ 3
< n30 ·⌈c⌉3 +20(n0 ·⌈c⌉)+1 =n3 +20n+1.
That is, n3 + 20n + 1 > c · n2, when n = n0 · ⌈c⌉. Which contradicts our assumption.
Hence, our assumption that T(n) ∈ O(n2) must be false, and therefore T(n) ∈/ O(n2), as required. QED.
(d) Prove that running time T (n) = n3 + 20n + 1 ∈ O(n4).
PART 4: Analyzing the Complexity of Programs………………………………………………… Consider the following problems from various domains within computer science and answer questions about the com- plexity and feasibility of the programs given to solve them. Remember:
Solution:
Proof: We prove this by direct proof.
BythedefinitionofBig-O,T(n)∈O(n3)iffthereexistsan0 ∈N,ac∈R+ foralln∈Nwithn≥n0,suchthat n3 +20n+1≤c·n4.
Notethat∀n∈N,n≥1,wehaven3+20n+1≤n4+20n4+1n4 =22n4.Hence,T(n)≤c·n4,∀n≥n0, withc=22andn0 =1andT(n)∈O(n4).QED.
g
O(1) O(log n) O(n) O(n log n) O(n2) O(n3) O(nr ) O(an) O(n!)
Rate of growth
constant logarithmic linear “n log n” quadratic cubic polynomial exponential factorial
Perfect Numbers
Discuss the following. A number for which the sum of all of its proper divisors is equal to itself is known as a perfect number. For example, the proper divisors of 6 are 1, 2 and 3 and 1 + 2 + 3 = 6. Another example is 28; the proper divisors
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 6: Undecidability and Complexity Page 9 of 9
of 28 are 1, 2, 4, 7 and 14, and 1 + 2 + 4 + 7 + 14 = 28. Hence, it should be clear that it is simple to test whether a given number is perfect or not: we find all the proper divisors, add them all up and then test if the sum is equal to the original number.
Consider the following program, where perfect(n) mis a function which returns true if n is perfect, and false otherwise:
n := 3; found := false;
while (not found) do
if perfect(n) then found := true
else n := n+2
(a) Does this program terminate or not?
(b) Is the problem of writing a program to determine whether there are any odd perfect numbers tractable, intractable, polynomial, undecidable, etc. Discuss and explain your views on this.
Solution: It is unknown whether there are any odd perfect numbers, though various results have been obtained. All perfect numbers are also Ore’s harmonic numbers and it has been conjectured as well that there are no odd Ore’s harmonic numbers other than 1.
So, we just don’t know whether the above program will terminate or not. Because of that we cannot state a running time complexity for such program: there is no function f (n) that we can prove whether it bounds the running time of the algorithm.
Solution: This one is a bit tricky. First, we need to be clear that programs and decision problems are not the same thing. Programs can solve decision problems. So it is wrong to say that a program is decidable or undecidable: only decision problems can be decidable or undecidable (depending whether there is a TM that solves it!).
So, regarding what the complexity is for the decision problem “is there an odd perfect number?”, we basically cannot state anything. To see this, imagine we change “perfect” to “prime”: “is there an odd prime number?”. Of course, the answer is YES!. So the prime-odd decision problem is decidable and is tractable because we can build an algorithm of constant running time that just writes “YES” (see no need to check any numbers!). So what would happen if tomorrow somebody finds a perfect odd number: what would be the complexity of the perfect-odd decision problem? What is somebody proves tomorrow that there is no odd perfect number?
If we knew whether there was an odd number or not, then the problem would be tractable and in fact would have constant complexity, as the program would just write “yes” or “no” as appropriate. In fact, there is either an odd perfect number or there is not. So either the machines that writes “yes” or that one that writes “no” would solve the decision problem in constant time; however we cannot say which is the right machine that solves the problem! Tricky question indeed…
Passwords
Below are some codes extracted from two different programs. Both of these programs can be used to check passwords consisting of 5 characters. Take a look at the source code, and answer the questions below.
Assuming a random password exists in an array password[].
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory
Tutorial 6: Undecidability and Complexity
Page 10 of 9
Program 1
#define SIZE 5
…
int i,j;
bool found[SIZE]; …
for i = 0 to SIZE do found[i] = false;
end for
for i = 0 to SIZE do
for j=0; j<26 and found[i]==false; j++ do if password[i]==’a’+j then
found[i]=true; end if
end for end for
Program 2
#define SIZE 6
...
int i,j,k,l,m;
char attempt[SIZE]; bool found=false; ...
for i=0; i<26 and found==false; i++ do for j=0; j<26 and found==false; j++ do
for k=0; k<26 and found==false; k++ do for l=0; l<26 and found==false; l++ do
for m=0; m<26 and found==false; m++ do attempt[0]=’a’+i;
attempt[1]=’a’+j;
attempt[2]=’a’+k;
attempt[3]=’a’+l;
attempt[4]=’a’+m;
if strcmp(password,attempt==0) then
found = true end if
end for end for
end for end for
end for
(a) How do the algorithms used by these two programs differ?
(b) Assume the maximum time it takes Program 1 to check a 5 character password is 6.5 milliseconds, what is the maximum time it will take to check a 10 character password?
Solution:
Program 1 loops through each character of the password array and verifies each position individually. Program 2 builds every possible combination and tests the whole password each attempt.
Solution:
The maximum time taken for Program 1 is when the password is ‘zzzzz’. This will involve 5 × 26 = 130 comparisons. Doubling the length of the password doubles the number of comparisons needed by Program 1
RMIT CT 2021 (Semester 2) -
COSC1107/1105 - Computing Theory Tutorial 6: Undecidability and Complexity Page 11 of 9
(10 × 26 = 260). If a 5 letter password takes 6.5 milliseconds, a 10 letter password will take 13 milliseconds (linear).
(c) Atarateof20operationspermillisecond,whatisthemaximumtimeitwilltakeforProgram2tochecka5character password? How about for a 10 character password?
(d) Still assuming a rate of 20 operations per millisecond, how long will Program 1 take to check a 5 digit password if the program becomes case sensitive? (i.e., the alphabet now consist of 52 characters instead of just 26)
(e) How long will Program 2 take to check a 5 digit password if it becomes case sensitive?
(f) Discuss the effects of increasing the password length, and the effects of increasing the alphabet size.
Primality testing
Consider the following algorithm:
prime(n): boolean
if n mod 2 == 0 then
return false end if
for i=3; i ≤ n/2; i+=2 do if n mod i == 0 then
return false end if
end for
Note that prime(7) performs 2 mod operations, one outside the loop and one inside it. Also note that prime(15) performs 4 mod operations (one outside the loop and three inside).
(a) Complete the following table, where mods(n) is the maximum number of divisions peformed by prime(n)
Solution:
The number of comparisons required by Program 2 for a password composed entirely of ‘z’s is 26n . For ’zzzzz’, 265 = 11, 881, 376 comparisons are required. At a rate of 20 operations per millisecond, this will take approxi- mately 10 minutes. For ‘zzzzzzzzzz’, 2610 = 1.4 × 1014 comparisons are required. At the same rate, this will take around 223 years.
Solution:
If Program 1 is case sensitive, at most 52 comparisons per character will be required. ‘ZZZZZ’ would require 52 ∗ 5 = 260 comparisons. At 20 operations per millisecond, this would take 0.013 seconds.
Solution:
If Program 2 is case sensitive, ‘ZZZZZ’ would take 525 = 25×265 = 380, 204, 032 comparisons. At 20 operations per millisecond, this would take approximately 5.3 hours.
Solution:
Program 1 is O(σn) where n is the length of the password, and σ is the size of the alphabet, so increasing either alphabet size or password length increases the time required linearly.
Program 2 has the complexity O(σn), so doubling the base will give complexity (2 × σ)n, but doubling the length will give σ2n = (σ2)n, and hence is the effect of squaring the alphabet size.
RMIT CT 2021 (Semester 2) -
COSC1107/1105 - Computing Theory Tutorial 6: Undecidability and Complexity
Page 12 of 9
n mods(n) ⌊log2(n) + 1⌋ ⌊log2(n) + 1⌋ - 2 4-7 2 3 1
8-15 4 4 2
16-31 8 5 3
32-63 64-127 128-255 256-511 512-1023 1024-2047 2048-4095
Solution: The n being an interval here refers to the fact that for an n between 4 and 7, prime(n) will do at most 2 mod operations. When n is between 8-15, it will do at most 4, and so on.
For example, the question says “note that prime(15) does 4 mod operations”, this is the maximum that is possible. We can easily check the others to see if they fit. For example:
prime(9):
9 mod2=1,sokeepgoing
i=3,9 mod 3=0returnfalse
so, prime(9) does 2 mod operations, which is definitely “4 or less”, so it holds.
When n is in the next bracket (16-31), then maximum number of operations will be 8, and so on. You can see that the size of the intervals in the left column are doubling with every step, and so is the maximum number of mod operations.
The column next to n is saying “take the floor of log2(n)+1”, and for any number in the intervals 4-7, 8-15, 16-31, etc - it will be the same as any number in that interval.
n mods(n) 4-7 2
8-15 4
16-31 8
32-63 16 64-127 32 128-255 64 256-511 128 512-1023 256 1024-2047 512 2048-4095 1024
⌊log2(n) + 1⌋ 3
4
5
6 7 8 9 10 11 12
⌊log2(n) + 1⌋ - 2 1
2
3
4 5 6 7 8 9 10
(b) Giventhatanumberncanberepresentedin⌊log2(n)+1⌋bits(i.e.3bitssufficefor0-7,4bitssufficefor8-15,etc.), what does this tell you about the complexity of this algorithm? (Hint: if the size of the representation of a number is increased by one bit, how does this increase the number of divisions?)
PART5: EstimationsofRunningTime.................................................................... By now you should be able to see that when describing the complexity of an algorithm, only the dominating terms are important. For example, if we have two algorithms with complexities n3 + n2 and n3 + 5 respectively, we can say that both of these algorithms have complexity O(n3). This is because n3 is the dominating term, and as the input size gets larger and larger, the effect of n2 and 5 will no longer be significant compared to the influence of the n3 term.
(a) Consider the following procedure:
Solution:
The two right hand columns above are trying to get you to think about these increasing intervals in a more systematic way. So, if we can represent any integer n by ⌊log2(n) + 1⌋ bits, what happens with each increase of the number of bits we need to represent n?
For example, we can represent 0-1 with 1 bit, 0-3 with 2 bits, 0-7 with 3 bits, 0-15 with 4 bits, 0-31 with 5 bits, etc etc.. what does that mean? It means the interval is doubling every time, like the left column. So, we can say that as we increase the number of bits by 1, the maximum number of mod operations that prime(n) will perform doubles.
RMIT CT 2021 (Semester 2) -
COSC1107/1105 - Computing Theory Tutorial 6: Undecidability and Complexity Page 13 of 9
collatz(n)
if n == 1 then halt
else if n is even then collatz(n/2)
else if n is odd then collatz(3n+1)
i. For what values of n does collatz(n) terminate?
ii. What is the computational complexity of collatz(n)?
(b) Given the algorithms with the following complexities:
1. 10n2 + 1000
2. n + log10(n)
3. ((n3 +2n)×(n+5))/(n2 ×n2)
4. 5n√n+5n2 +25
5. n!+n10
i. Calculate how many operations the following algorithms require for the case n = 50
ii. Reduce the functions above to express the complexity of the algorithm in big O notation
iii. Calculate the number of operations again using the reduced functions.
iv. Compare your answers
End of tutorial worksheet
Solution:
The conjecture is that no matter what number you start with, you will always eventually reach 1.
If the Collatz conjecture is true, the program will always halt (stop) no matter what positive starting integer is given to it. However, we don’t know whether it is true, so we cannot assign a complexity as the program may run forever.
Some students will find that if the input is of the form 2n, then the algorithm does terminate. This is fine, but see that in order to ascribe a running time complexity to the algorithm, it needs to account all inputs.
Solution:
1. 10n2 + 1000: 26,000 operations
2. n + log10(n): 52 operations
3. ((n3 + 2n) × (n + 5))/(n2 × n2): 1 operation 4. 5n√n + 5n2 + 25: 14,293 operations
5. n! + n10: 3.04 × 1064 operations
Solution:
1. 10n2 + 1000: O(n2)
2. n + log10(n): O(n)
3. ((n3 + 2n) × (n + 5))/(n2 × n2): O(1). This function decreases as n increases, and has an asymptote
of 1.
4. 5n√n + 5n2 + 25: O(n2)
5. n! + n10: O(n!)
Solution:
1. n2: 2,500
2. n: 50
3. 1: 1
4. n2: 2,500
5. n!: 3.04 × 1064
Solution: By experimenting with a different constant value for each of the above simplified functions, it can be verified that for values greater than an input value n0, the order of magnitude function multiplied by the constant will always return a value greater than that returned by the original function. That is, the order of magnitude function multiplied by some constant will form an upper bound for the original function.
RMIT CT 2021 (Semester 2) -