COSC1107/1105 Computing Theory
School of Computing Technologies Semester 2, 2021
Tutorial No. 10: Computational Complexity and Computability
The aim of this tutorial is to introduce you to the fundamentals of computational complexity.
PART1: Complexity…………………………………………………………………………….. (a) Complete the following table. You may find that some values require a spreadsheet to calculate.
Algorithm Operations n=5 n=10 n=20 n=30 n=40 n=50 n=100 1n
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n+5 2n n2
n2 + n 2n
2n + n 2n + n2 2n + n6 n! n!+n2 n!+2n nn nn+n2 nn+2n nn + n!
Solution:
Operations n = 5 n = 10 n = 20 n = 30 n = 40 n = 50 n =
1
2
3
4
5
6
7
8
9
10
11
12
100 n 5 10 20 30 40 50 100
n+5 10 2n 10 n2 25
n2 + n 30 2n 32 2n + n 37 2n + n2 57
2n + n6 15657 n! 120 n! + n2 145 n! + 2n 152
15 25 35 45 55 105 20 40 60 80 100 200
100
110
1024
1034
1124
1001024
3628800
3628900
3629824
400
420 1048576 1048596 1048976 65048576 2.43 × 1018 2.43 × 1018 2.43 × 1018
900
930 1073741824 1073741854 1073742724 1802741824 2.65 × 1032 2.65 × 1032 2.65 × 1032
1600
1640
1.10 × 1012 1.10 × 1012 1.10 × 1012 1.10 × 1012 8.11 × 1047 8.11 × 1047 8.11 × 1047
2500
2550
1.12 × 1015 1.12 × 1015 1.12 × 1015 1.12 × 1015 3.04 × 1064 3.04 × 1064 3.04 × 1064
10000
10100
1.27 × 1030
1.27 × 1030
1.27 × 1030
1.27 × 1030
9.33 × 10157
9.33 × 10157
9.33 × 10157 0200
0200 0200 0200
13 nn 3125 10000000000 1.04 × 1026 2.05 × 1044 1.21 × 1064 8.88 × 1084 > 1
14 nn + n2 3150 10000000100 1.04 × 1026 2.05 × 1044 1.21 × 1064 8.88 × 1084 > 1
15 nn + 2n 3157 10000001024 1.04 × 1026 2.05 × 1044 1.21 × 1064 8.88 × 1084 > 1
16 nn + n! 3245 10003628800 1.04 × 1026 2.05 × 1044 1.21 × 1064 8.88 × 1084 > 1
1
COSC1107/1105 – Computing ThTeuotroyrial 7: Computational Complexity and Computability (b) Group Algorithms 1-16 into the appropriate places in the table below.
Page 2 of 4
Class
Linear Quadratic Exponential Factorial ’Hyperfactorial’
Big O
O(n) O(n2) O(2n) O(n!) O(nn)
Algorithm/s
Solution:
Class
Linear Quadratic Exponential Factorial ’Hyperfactorial’
Big O
O(n) O(n2) O(2n)
O(n!) O(nn)
Algorithm/s 1,2,3
4,5
6,7,8,9 10,11,12 13,14,15,16
(c) Assume that each operation in the table above takes 2 milliseconds. At what point (if any) does the time take to execute each algorithm exceed 10,000 hours? (ie 3.6 × 107 seconds, or about 1.14 years).
(d) Assume that in 5 years time from now, processor speeds have increased dramatically, so that processor power will be 1,000 times faster than it is now (!!). This means that the each operation in the above table will now take 2 microseconds (i.e. 1,000 time faster then 2 milliseconds). How does that change the analysis of the previous question?(i.e. at what apoint (if any) does the time taken to execute each algorithm exceed 10,000 hours).
(e) Three programs had their execution times (in seconds) measured on the same data resulting in the table below.
n Program 1 Program 2 Program 3 (seconds) (seconds) (seconds)
1535 27 6 12 311 11 31 419 18 68 535 27 129 667 38 220 7 131 51 347
Based on this data:
i. Classify each of Program 1, Program 2 and Program 3 as either tractable or intractable. Briefly explain your
answer.
ii. Calculate the time required for Program 1 for n = 10.
Solution: A spreadsheet is the simplest way to do this. A summary is below. Mor precise values can be calculated in each case.
Algorithm 1,2,3,4,5
6,7,8,9 10,12,13,14,15,16
N
never (ie not up to 100) between 30 and 40 between 10 and 20
Solution: Not much changes!
Algorithm 1,2,3,4,5
6,7,8,9 10,12,13,14,15,16
N
never (ie not up to 100) between 40 and 50 between 10 and 20
Solution: Program 1 has complexity 2n + 3 and hence is intractable. Program 2 has complexity n2 + 2 and hence is tractable. Program 3 has complexity n3 + 4 and hence is tractable.
RMIT CT 2021 (Semester 2) – Exercise 1 continues on the next page. . .
COSC1107/1105 – Computing ThTeuotroyrial 7: Computational Complexity and Computability Page 3 of 4
Solution: When n = 10, Program 1 takes 210 + 3 = 1027 seconds.
iii. Calculate the value of n for which Program 1 executes in the same time that Program 2 takes for n = 10.
iv. Calculate the value of n for which Program 1 executes in the same time that Program 3 takes for n = 10.
(f) Briefly explain the difference between tractable, intractable and undecidable problems.
(g) The Chess may find the following formulae useful in answering this question.
n 1+2+4+8+…+2n = 2i =2n+1 −1
i=1
Solution: When n = 10, Program 2 takes 102 + 2 = 102 seconds. For Program 1, solving 2n + 3 = 102 gives n = 6.63, so n = 6 (so that we can guarantee Program 1 will complete in this time).
Solution: When n = 10, Program 3 takes 103 + 4 = 1004 seconds. For Program 1, solving 2n + 3 = 1004 gives n = 9.96, so n = 9 (so that we can guarantee Program 1 will complete in this time).
Solution: A tractable problem is one that can be solved in polynomial time. An intractable problem is one that can only be solved in exponential time or worse. An undecidable problem is one for which there is no algorithm.
a+ar+ar2 +…+arn = 1+2+3+4+…+n= i=n(n+1)/2
i=0
n a(rn+1 − 1)
ari−1 = r−1 n
i=1
A travelling wizard arrives at the court of a king, who is very keen on the game of chess. The king was an excellent player, and offered a substantial award to anyone who could defeat him. The wizard, of course, did so easily, and hence claimed his reward, asking the king to choose between the two following alternatives.
• 10 billion gold coins (i.e. 1010 gold coins)
• 1 gold coin for the first square on the board, 2 for the next, 4 for the next, 8 for the next, and so on, for all 64
squares.
i. Which option is cheaper for the king? By how much?
ii. If the wizard were to settle for less than 64 squares (so that only the first m squares count), what is the largest number of squares that makes the first option the cheaper one?
iii. If the king says he cannot afford the full amount by the second method, and offers to pay half of this amount, how many squares does this correspond to?
iv. Ifthekinginsteadoffers100coinsforthefirstsquareandthen10%extraforeachsubsequentsquare,howmuch will this cost?
v. If the king were to offer 1 coin for the first square, 2 for the next, 3 for the next, 4 for the next, and so forth, how much would this cost?
Solution: The first option is cheaper by a very long way! There are 8 × 8 = 64 squares on a chess board. 1+2+4+8+…+263 = 264 −1 = 18,446,744,073,709,551,615, or 1.8×1019. In comparison, 10 billion is 1 × 1010. So the second one is about a billion times better!
Solution: We want the largest m such that 1 + 2 + . . . + 2m−1 < 1010. As the sum is equal to 2m − 1, we want the largest m such that 2m − 1 < 1010. This gives us m = 34.
Solution: Half of the full amount is 9, 223, 372, 036, 854, 775, 807 (rounding down by half a coin). So we have 1 + 2 + ... + 2k−1 = 2k − 1 = 9,223,372,036,854,775,807, so 2k = 9,223,372,036,854,775,808, making k = 63.
Solution: The sum is now 100 + 100 × 1.1 + 100 × 1.12 + ... + 100 × 1.163 = 100(1.164 − 1)/(0.1) = 1000 × (1.164 − 1) = 444, 792
RMIT CT 2021 (Semester 2) - Exercise 1 continues on the next page. . .
COSC1107/1105 - Computing ThTeuotroyrial 7: Computational Complexity and Computability Page 4 of 4
Solution: Thesumisnow1+2+3+...+64=64×65/2=2,080.
vi. If the king to pay for the black squares only (assuming the sequence starts on a white square) how would this
change the answers to the two previous questions?
vii. Find the smallest value of n such that the wizard should take n2 coins rather than 10 billion. Solution: Wewantthesmallestnsuchthatn2 >1010,son>105.Thismeansn=100,001.
viii. Find the smallest value of n such that the wizard should take n! coins rather than 10 billion.
(h) Passwords
Saruman the Dodgy is a security expert at Passwords R Us. Saruman is increasingly concerned about a number of his colleagues who use passwords with a maximum length of 6 and using only lower case letter (ie only the letters a − z). “Such passwords can be easily cracked; you must use at least 10 characters and a mixture of upper and lower cases letters. Better still, include digits as well, and at least one character which is not alphanumeric (i.e. one that is not a letter and not a digit)”, thunders our hero.
i. To investigate these claims, complete the table below. Assume that passwords can be tested at the rate of one per 20 microseconds.
Solution: Forthefirstsum,thiswouldbe100×1.1+100×1.13 +100×1.15 +…+100×1.163 = (100 × 1.1)((1.12 )32 − 1)/((1.1)2 − 1) = 110 × (1.164 − 1)/0.21 = 232, 986.
For the second sum, it would be 2+4+6+8+. . .+64 = 2×(1+2+3+4+. . .+32) = 2×32×33/2 = 1056
Solution: Wewantthesmallestnsuchthatn!>1010.As13!=6,227,020,800and14!=87,178,291,200, this means n = 14.
No. Type
1 Lower case only (a-z)
2 Lower and upper case only (a-z,A-Z)
3 Alphanumeric (a-z,A-Z,0-9)
4
Length
6 7 8 9 10
Solution:
No.
1 2 3 4
Length
6 7 8 9 10
6178
395412
1136005
2352980
160636
20561434
70432292
164708600
4176541
1069194571
4366802112
11529602000
108590074
55598117673
270741730925
807072140000
2823341913
2891102118981
16785987317367
56495049800000
Here is the same table in more intuitive units, (hours, days and years when appropriate). No. — Length
6 7 8 9 10
1 1.72 hours
2 4.58 days
3 13.15 days
4 27.23 days
44.62 hours 237.98 days 2.23 5.22 years
48.34 days 33.88 years 138.38 years 365.35 years
3.44 years 1761.80 years 8579.29 years 25574.57 years
89.47 years 91613.50 years 531915.84 years 1790220.10 years
ii. Assuming that Saruman’s listeners only heed the advice about the length of the password, how much more secure is a password of length 10 compared to length 6 if only lower case letters are used?
Solution: Thisisacomparisonof2,823,341,913secondsvs6178seconds,oraboutafactorof2823341913/6178= 456976. So it is about 450,000 times more secure (!!).
iii. If instead they only heed the advice about including alphanumeric characters and one ’extra’ character, how much more secure is a password of length 6 compared to lower case only?
iv. Saruman makes a further pronouncement that in order to be safe, it is best to use a password that will take any cracker at least 1 year to crack (so that a policy of changing passwords every six months will defeat any such attempts). According to this standard, which of the above combinations are safe? Which are not?
Solution: This is a comparison of 2,352,980 seconds vs 6178 seconds, or about a factor of 2352980/6178 = 380.8. So it is ’only’ about 380 times more secure.
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing ThTeuotroyrial 7: Computational Complexity and Computability Page 5 of 4
Solution:
No. Length
6 7 8 9 10
1 Unsafe
2 Unsafe
3 Unsafe
4 Unsafe
Unsafe Unsafe Unsafe Safe Safe Safe Safe Safe
Safe Safe Safe Safe Safe Safe Safe Safe
v. Saruman discovers from one of his many spies that the estimated rate of password testing of 20 microseconds is too high, and that a more realistic figure is 6 microseconds. Saruman then decrees that all calculations should assume a rate of at most 2 microseconds. How does this change the analysis of the previous question? (ie which of the safe combinations are now unsafe).
vi. Some people presumably followed Saruman’s advice in full, i.e. ended up with a password with alphanumeric characters plus extra characters, and of length at least 10. If they don’t change their password for several years, presumably the ability to crack passwords will increase in that time. Let us assume that the speed of password cracking is 2 × 10−6 × (0.9)n, where n is the number of years from now.
For how many years will these passwords remain secure?
You may want to read about a related issue discussed by RMIT graduate here. (i) Filling a bag
Assume you have a bag and a number of items, each weighing a different amount. The bag has a specific weight limit that it can carry. The problem is to determine the selection of items is that is equal to the bag’s capacity.
For example, consider a bag with capacity 11kg, and five items each weighing 2kg, 3kg, 5kg, 7kg and 8kg. To completely fill the bagg in this case, we should put the 8kg and 3kg items in it.
i. Work out the way to completely fill the bags for each of the following cases. Bag Items
12 2,3,6,7
25 3,4,6,8,13
50 8,9,11,18,24,35
57 3,8,12,19,27,33
64 2,8,14,15,18,23,27,31
ii. What method did you come up with for this? Is your algorithm tractable or intractable? How long would it take to determine if no solution existed?
Solution: Redoing the table at 2 microseconds rather than 20 microseconds gives the following. No. Length
6 7 8 9 10
1 Unsafe
2 Unsafe
3 Unsafe
4 Unsafe
Unsafe Unsafe Unsafe Unsafe
Unsafe Unsafe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe
Solution: We want the smallest value of n such that 2 × 10−6 × (0.9)n × 7010 < 31557600, as 31557600 = 3600 × 24 × 365.25, i.e. the number of seconds in a year.
This means we need (0.9)n × 5649504980000 < 31557600, and so (0.9)n < 0.0000055859, and so n < log(0.0000055859)/ log(0.9) = 114.8 years. So their password is likely to last well into their descendants’ lifetimes, let alone their own!
Solution:
Bag Items
12 2+3+7
25 4+8+13
50 8+18+24
57 3+8+18+27
64 2+8+23+31 = 15+18+31 = 14+23+27 = 8+14+15+27
Solution: Almost certainly intractable, short of a genius-level discovery! This is a variation of the bin-packing problem, which is NP-complete (and hence almost certainly intractable). To see how an exhaustive search is
RMIT CT 2021 (Semester 2) -
COSC1107/1105 - Computing ThTeuotroyrial 7: Computational Complexity and Computability Page 6 of 4
exponential, consider setting a boolean flag whether or not each number is used in the sum. For n numbers, this gives 2n possible solutions.
RMIT CT 2021 (Semester 2) -
End of tutorial worksheet