INTRODUCTION |
Increasingly many problems can be solved with clever computer programs. In this chapter, however, you will be confronted with questions that can be simply formulated but that may never be algorithmically solvable, despite the rapid evolution of computers and enormous scientific effort.
|
UNSOLVABLE PROBLEMS |
There are still some problems that are unsolved, even though they are easy to formulate and especially important in practice. One of these, known as the subset sum problem, can be described as follows [more...The partial sum problem is a special case of the knapsack problem
from gamegrid import * import itertools coins = ["one", "two", "five", "ten", "twenty", "fifty"] def value(coin): if coin == "one": return 1 if coin == "two": return 2 if coin == "five": return 5 if coin == "ten": return 10 if coin == "twenty": return 20 if coin == "fifty": return 50 return 0 def getSum(moneybag): count = 0 for coin in moneybag: count += value(coin) return count def showMoneybag(moneybag, y): x = 0 for coin in moneybag: loc = Location(x, y) removeActor(getOneActorAt(loc)) coinActor = Actor("sprites/" + coin + "cent.png") addActor(coinActor, loc) x += 1 addActor(TextActor(str(getSum(moneybag))), Location(x, y)) makeGameGrid(8, 20, 40, False) setBgColor(Color.white) show() n = 6 k = 1 while k <= n: combinations = list(itertools.combinations(coins, k)) setTitle("(n, k) = (" + str(n) + ", " + str(k) + ") nb = " + str(len(combinations))) y = 0 for moneybag in combinations: showMoneybag(moneybag, y) y += 1 getKeyCodeWait() removeAllActors() k += 1
|
MEMO |
The combinations of k elements that you can build from a list of n, are easily retrievable with the function combinations() from the module itertools. You have to convert the return value to a list, from which the found combinations can then be retrieved (as tuples). As you can see, the obtained combinations are ordered in a way similar to how you would reasonably order them by hand. You can calculate the number of combinations of n elements to the order k as follows, as you know: where n! is the factorial, meaning the product of all numbers from 1 to n. In our case n = 6 can result in 6, 15, 20, 15, 6, 1, so a total of 63 combinations. |
from gamegrid import * import itertools coins = ["one", "one", "one", "two", "five", "five", "ten", "ten", "ten", "ten", "twenty", "twenty", "fifty", "fifty", "fifty"] def value(coin): if coin == "one": return 1 if coin == "two": return 2 if coin == "five": return 5 if coin == "ten": return 10 if coin == "twenty": return 20 if coin == "fifty": return 50 return 0 def getSum(moneybag): count = 0 for coin in moneybag: count += value(coin) return count def showMoneybag(moneybag, y): x = 0 for coin in moneybag: loc = Location(x, y) removeActor(getOneActorAt(loc)) coinActor = Actor("sprites/" + coin + "cent.png") addActor(coinActor, loc) x += 1 addActor(TextActor(str(getSum(moneybag))), Location(x, y)) makeGameGrid(15, 20, 40, False) setBgColor(Color.white) show() target = 100 k = 1 result = [] count = 0 while k <= len(coins): combinations = tuple(itertools.combinations(coins, k)) nb = len(combinations) for moneybag in combinations: count += 1 count = getSum(moneybag) if count == target: if not moneybag in result: result.append(moneybag) k += 1 y = 0 for moneybag in result: showMoneybag(moneybag, y) y += 1 setTitle("Step: " + str(count) + ". number of solutions for the count " + str(target) + ": " + str(len(result)))
|
MEMO |
With only 15 coins there are already 32,767 steps necessary in order to solve the subset sum problem using the enumeration method. Your enjoyment of solving problems with the computer is unfortunately spoiled once you try with a slightly larger purse of money, let's say 50 or 100 coins. If you count the necessary steps it takes for a purse with n coins and display them in a graph, there is a downright combinatorial explosion at n = 20 and you reach the limit of what is possible [more... Other limits you see in the book "Hromkovic, Seven Wonders of the computer science"]. |
from gpanel import * from math import factorial z = 100 def nbCombi(n, k): return factorial(n) / factorial(k) / factorial(n - k) makeGPanel(-5, 55, -1e5, 1.1e6) drawGrid(0, 50, 0, 1e6, "gray") setColor("black") lineWidth(2) for n in range(2, z + 1): count = 0 for k in range(1, n): count += nbCombi(n, k) print "n =", n, ", nb =", count if n == 2: move(n, count) else: draw(n, count) print "Runtime with 10^9 operations per second:", count / 3.142e16, "years" print "or:", int(count / 2e20), "times the age of the universe" |
MEMO |
Using the enumeration method, the subset sum problem is already unsolvable at relatively small amounts of elements, even though the method of solving is known. Hence the question arises whether there could be much better algorithms to solve the problem, the number of steps or complexity of which is a power of n (thus polynomial), just as the ones in the previous chapter for sorting. Unfortunately, until today no one has succeeded in finding such an algorithm for the subset sum problem and one assumes that there is none. However, there is also no theoretical proof for this assumption. At least we know today from the theoretical computer science that there are many similarly difficult problems and that one could expect to solve all these problems in one shot with polynomial complexity, if one finds such a solution for one of them [more... We call this class of problems NP-complete]. |
UNDECIDABLE PROBLEMS |
The limits of the human mind and computer technology are also visible in a context different from complexity. The mathematician and number theorist Lothar Collatz examined certain sequences of natural numbers and in 1939 he formulated the following question: Begin from any initial number n and build the following numbers according to these rules:
Question: Does this sequence always reach 1 for any possible starting number n? Collatz and many other number theorists and computer scientists have searched for a solution to this, because even the largest and fastest computers continuously yield sequences that arrive at the result 1. (The series does not converge because it endlessly repeats through the sequence 4, 2, 1). Therefore, it seems likely that the following theorem applies: The 3n+1 series reaches the number 1 for all natural starting numbers n after a finite number of steps. You can run through the 3n+1 series with a computer program for an arbitrarily settable starting number. from gpanel import * def collatz(n): while n != 1: if n % 2 == 0: n = n // 2 else: n = 3 * n + 1 print n, print "Result 1" while True: n = inputInt("Enter a start number:") collatz(n)
|
MEMO |
In Python you can even run through the 3n+1 series with large starting numbers and you will find that you always land at 1. Of course you have not proven the assumption this way. |
from gpanel import * def collatz(n): nb = 0 while n != 1: nb += 1 if n % 2 == 0: n = n // 2 else: n = 3 * n + 1 return nb z = 10000 # max n yval = [0] * (z + 1) for n in range(1, z + 1): yval[n] = collatz(n) ymax = (max(yval) // 100 + 1) * 100 makeGPanel(-0.1 * z, 1.1 * z, -0.1 * ymax, 1.1 * ymax) title("Collatz Assumption") drawGrid(0, z, 0, ymax, "gray") for x in range(1, z + 1): move(x, yval[x]) fillCircle(z / 200)
|
MEMO |
Collatz's assumption is a stubborn problem. If the assumption really is true, then it cannot be proved by conducting computer tests with increasingly larger starting numbers. It is even possible that the assumption is true, but a proof will never be found. In 1931 the mathematician Kurt Gödel showed with the incompleteness theorem that there can be correct propositions in a theory, whose correctness can, however, not be proven. Collatz's assumption can also be formulated as a decision problem: Does an algorithm that calculates the terms of the 3n+1 progression and stops at 1, really stop for any possible initial values? You could try to solve this question with a computer. Unfortunately, this could be hopeless too, since the great mathematician and computer scientist Alan Turing has already proved with the halting problem that there will never be a general algorithm that allows you to decide if any given program with arbitrary input really stops. Collatz's assumption of 3n+1 could thus indeed be true, but an undecidable problem. |