Beauty is in the Mind of the Beholder
Often mathematicians speak of finding beauty in their subject, it is reasonable to ask what they mean. Of course, one will get as many answers as there are maths practitioners, but I shall hazard a generalized answer here. Mathematicians deal with abstract objects that exist in the mind, and share a suspicion that these abstractions are in fact real. So like real things they have properties, and enter into relationships. The feeling is that if abstractions behave as real things, then they must themselves, at some level, be real. If they are real, then they must also have relations with other concrete things, and indeed, the ultimate aspiration is to develop an abstraction that describes the world. This is the fundamental quality that separates the practice of maths from, say, intellectual games. Our minds evolved to find order in the universe and mathematics gives us as systematic and dependable (to some extent) way of doing so. Absence of clarity causes anxiety. As clarity is gained, anxiety evaporates and beauty is discovered. And like all beauty with meaning, it does not readily appear to the mind, but rather, it is an acquired taste. To see the world through the tools of mathematics requires a great deal of effort and time. One cannot get away with a shallow gaze at the matter, but must completely submerse oneself in it in order for the the abstract to gain dimension and become real to the mind. One must be willing to take many mental walks into the abyss and with time, the beauty therein becomes apparent.

It is no different for computational complexity. But in this case we are at an advantage because this walk, the walk from the real to the abstract and back can be greatly aided by intuition. The subject constructs new abstract notions directly from familiar, more accessible ones.

Suppose it is 2000 B.C and I have acquired the ability to count but have yet to learn how to add. If I have, say 23 objects, and a friend gives me an additional 45, how many do I have now? If I want an answer, then I have a problem. In fact I have at this point discovered the class of addition problems, for which my specific situation is but an instance in this class. Stated explicitly, how do I get the total of two numbers? If I find a strategy for addition , then I can solve all instances of the addition problem. My first option is to recount everything so as to know exactly how many objects I now possess. I will physically count everything. This is a legitimate addition problem strategy because it can solve all instances of the addition problem.

Suppose I now have, say 235 objects, and I am expecting 432 more in addition. Knowing my strategy to be time consuming, I may very well worry. So I ask myself how others who handle big groups of things manage the problem. I know the tax collector deals with far more objects than I, so I pay her a visit and relay my situation. The tax collector is indeed able to help. She introduces me to the adding strategy. Given the structure that we use to represent numbers, I can obtain the total of any two numbers by doing a column-wise addition from right to left and carrying forward where necessary. The important difference here is that the addition strategy is more efficient, in comparison to counting as the number of items grow. The important concept is how to distinguish between efficient and inefficient solution strategies. In general, efficient strategies manipulate some inherent property of the problem at hand, in this case, number representation, and inefficient methods tend to be some kind of exhaustive search over a set, as in recounting all objects.

Thinking in simple terms, my addition would require 667 basic operations; counting each object; while the new method requires at most 5. If we set each operation to take the same time or impose a linear relationship between the two, then it is easy to see that the new method is a lot better in terms of number of operations and consequently, time. Consider that I increase additional objects from 432 to 600, counting now takes 835 operations while the addition strategy still takes at most 5 operations. This is at the heart of computational complexity.

Suppose I now want to add 235 objects 432 times, what do I do? Sure, the adding method could work, but it would take a lot of time. Again I inquire with the tax collector and, again, I am not disappointed. I am introduced to the long multiplication method. Using addition, I could add 432 to itself 235 – 1 times. Using long multiplication, I can again take advantage of the structure of number representation and achieve my goal quickly. Essentially, the long multiplication method is a more efficient method for solving all instances of the multiplication problem than the repetitive adding method. But we want to express this more formally, so we relate resources taken to solve a problem to the size of input. Here we must make certain things clear:

• We will consider input size to be the number of digits of the input in binary form, chains of 1’s and 0’s. In my multiplication example above 235 is 11101011 and 432 is 110110000 in binary form. So n would be 8 and 9 respectively. We can make the input strings the same length by adding 0’s in front of the shorter ones to consider worst case scenarios. Note that the only difference is that because we are using fewer symbols we have longer representations, but the arithmetic remains the same and so does the pattern of resource consumption as n increases.
• As stated above, when we speak of input size n, we will be considering the number of digits, not the absolute value of the input, so binary numbers 100 and 101 will both have n = 3. If I increase input n by 1, I am considering inputs with 4 digits, and not the values 101 or 110. This is because its convenient to do so and what ever method of solving a problem is incorporated, the procedure will work with a character of the input at a time.
• In complexity we mostly consider the function O(n), which gives the worst case running time for a given solution strategy. This is considered prudent since our process will not take more than O(n) to run and halt. We can easily capture the number of operations with time since we can set a single operation to take some constant time. In my multiplication example above, for the repeated addition strategy O(n) is 2ⁿ and for the multiplication strategy O(n) is n². We want to be able to make reliable conclusions about the algorithms. Generally, ∃ n₀ ∈ N such that

2ⁿ ≥ n²

for all n ≥ n₀.

We have just converted a notion into a formal relationship and we can now confidently make conclusions about the two algorithms, i.e. as n gets larger and larger, repetitive addition takes increasingly longer than the multiplication strategy.

When I wanted to know if two numbers could be multiplied together, I was asking a computation question. Computability is concerned with the question does a given problem have a solution strategy that solves all its instances and halts. A computable problem is one which we can solve by mechanically following a set of procedures and getting the correct answer. When I wanted to know how long a given strategy takes to solve a problem, I was asking a complexity question. Complexity is concerned with computability given limited resources. Its aim is to understand and contextualize the notion of efficiency. The goal of computational complexity is to develop a comprehensive classification of problems according to the relative amount of computational resources needed to solve them.

Rise of the Machines I

Our first task is to familiarize ourselves with the tools and notations of the subject. If some of these seem confusing at first just go through them, and go through them again as you encounter their use in this and other articles to come:

A problem Q is a binary relation on a set I of problem instances and a set S of problem solutions i.e. each element in the relation is an ordered pair (i, s) with i ∈ I and s ∈ S.

An alphabet Σ is a finite set of symbols.

Let Σ be a finite alphabet of symbols, by Σ^∗ we mean the set of all finite strings (including the empty string) consisting of elements of Σ. By language over Σ we mean a subset L ⊆ Σ^∗ . For a string x ∈ Σ^∗ , we denote the length of x by |x|.

A function problem is a function from strings to strings f : Σ^∗ → Σ^∗.

A decision problem is a function from strings to Boolean values f : Σ^∗ → {0, 1}.

A language associated with a given decision problem f is the set {x ∈ Σ^∗ |f(x) = 1}.

The set of all binary strings of length n is denoted by {0, 1}ⁿ , while the set of all binary strings is denoted by {0, 1}^∗ = ∪_n≥0 {0, 1}ⁿ.

An algorithm is the process of verifying that a given string belongs to the associated language in order to solve a relevant problem.

A Turing Machine is a mathematical model that can simulate arbitrary algorithms.

More completely, a Turing Machine is a 7-tuple number, Q, Σ, Γ, δ, q₁ , q_accept , q_reject, where Q, Σ, Γ are all finite sets.

1. Q set of states

2. Σ is the input alphabet not containing blank b

3. Γ is the tape symbol, with b ∈ Γ and Σ ⊆ Γ

4. δ : Q × Γ → Q × Γ × (L, R, S) is the transition function with right, left and stay commands

5. q₁ ∈ Q is the initial state

6. q_accept ∈ Q is the accept state

7. q_reject ∈ Q is the reject state, and q_accept != q_reject

The configuration of a Turing machine at any given time consists of current state, current head position and current tape contents. Three outcomes are possible when a Turing machine processes an input; the machine may accept, reject or loop, (not halt). So for w !∈ L(M ) Turing machine M can fail to accept w by either entering into a q_reject state or by looping.

If a Turing machine halts at all inputs, it is called a decider for a given language L. A decider decides on all languages it recognizes.

As you may have realized by now, algorithms have been used to solve problems for thousands of years and my solutions to addition and multiplication were algorithms at work. More interesting algorithms would be Euclid’s method for finding the greatest common divisor of two numbers, or finding the shortest distance between a set of towns. The formal definition of algorithm is attributed to Alan Turing who in 1936, described algorithms using Turing machines. We can use the following schema:

Problems are languages over a finite alphabet and Algorithms are executed by
Turing machines

A Turing machine can be built to simulate any physically releasable computational model. This means that given any machine that solves a real world problem, a Turing machine can be constructed to simulate that machine regardless of how complicated it may be. The word machine here is used to describe a mechanical, step-by-step method of solving problems. Notice this is really an algorithm. Essentially, a Turing machine is a thought process that models the notion of ’computation’ rather than a ’computer’ itself. So if I can multiply 5 and 2 mechanically, I can also design a Turing machine to do that, if I can use an abacus to add 35 and 47, so can a Turing machine, if I can build a computer that can load an operating system, open a browser and read documents on the internet, I can also construct a Turing machine equivalent. Such is its power.

Why is this important? It is important because we want to measure the performance of algorithms and classify them accordingly, regardless of the computational model utilized. To do this we need a generalized computational model so that we can theoretically analyse any computation done by any model. Since Turing machines are polynomially equivalent to other practical computational models, they give us a universal means for this analysis.

In the next article we will explore the workings of a Turing machine more closely.