Problems, Computers, and Computer scientists
Kamal Lodaya, Venkatesh Raman, R. Ramanujam, The Institute of Mathematical Sciences, Chennai
Can a computer solve any problem? Will robots take over the world? How does Google list so many relevant pages within seconds when you type in a query? Is there one giant computer where Google stores all the information in the world?
We have often heard many such questions from readers of Jantar Mantar and other high school students. Some of these questions are easy to answer, some not so easy. Computer scientists not only build computers and write programs, but think about such questions too. Theoretical computer science tries to think about computing in mathematical terms, not worrying about technology. It is an active area of research at IMSc.
Why should one think about computers mathematically? So that we can think of not just tomorrow's computers, but even that of the next century! In fact the first mathematical model of a computer was given by Alan Turing in 1936, long before computers (or even electronics) existed. In fact it was the mathematical model that drove the construction of computers in 1950s. Similarly, scientists had developed the tools for distributed computing in the 1970s when even wired connections between computers was difficult, but those tools led to the Internet we use today.

Computers and algorithms
Mathematicians have always thought about "computers" in the sense of coming up with {\bf algorithms} or methods to solve problems. (See box for a description of the word algorithm). We all encounter algorithms in school: to multiply two 3-digit numbers, long division, adding fractions, solving two linear equations in two variables, finding x-y intercepts, etc. While working out an algorithm somebody teaches you is boring, finding new algorithms, comparing them, arguing that what you have is the best possible one is great fun. Can you imagine trying to show that there is NO algorithm to solve some particular problem? This is indeed what theoretical computer scientists do.
For instance, human beings have studied prime numbers for more than 2000 years. In school we all learn an algorithm to check if a number is prime. Quickly answer: is 143 a prime? You say no, since 11 X 13 = 143. What about 10007? It happens to be prime, but surely it takes you a lot of effort to check this. Is there a {\em fast} algorithm to check if a number is prime? This was a question that interested mathematicians for a long time, and only in 2002 such an algorithm was given, by Manindra Agrawal, Neeraj Kayal and Nitin Saxena of IIT-Kanpur. (While Agrawal was a professor, both Kayal and Saxena were only 20 years old. So just think, perhaps you can solve such problems too, in just a few years' time!)

BOX What is an algorithm
An algorithm for a problem is a step by step description, such that if you follow it, you get an answer within a finite number of steps. There can be many different algorithms for the same problem (for example, sorting a list of numbers).
The name algorithm comes from Muhammad ibn Musa al-Khwarizmi (9th century CE), whose book, {Kitab al-mukhtasar fi hisab al-jabr wa'l muqabala} ({Compendium on calculation by force and contest}) gave algorithms to solve linear and quadratic equations. These ideas had originally been developed in India, but this was the first textbook on the subject, written in Arabic. It led to the development of algebra.
A ruler-and-compass construction can be thought of as a kind of algorithm using algebra for problems in geometry. There are more general kind of algorithms which tackle problems in other areas.
END OF BOX
Is this true?
Alan Turing, 1936, formalized the notion of a general algorithm (not just in algebra) and showed that:
There is {no} algorithm to check whether a logical sentence, even one purely about arithmetic, is always true.
Consider a sentence which says: There are infinitely many prime number pairs n and n+2. What does this sentence mean? Take a number, n=3. Then n+2=5. The pair (3,5) are both prime, and are separated by 2 units. This sentence then says that there are infinitely many such pairs.
Many mathematicians believe the answer to the question for this sentence is yes. But so far no one knows whether this sentence is true.
How fast are fast algorithms?
We spoke of fast algorithms. But how fast is fast? Does it not depend on technology whether a computer is fast or not? One mathematical way to do this is to fix up some number n for each problem and ask how much time is needed to solve the problem as a function of n. If that function grows as a power of n, say, n^2, n^3 or even n^100 it is alright. But if it needs exponential amount of time, we consider it too slow. The difference is between polynomials and exponentials.
Interestingly, when no fast algorithm is known for a problem, we can use that information too! No fast algorithm is known for finding factors (divisors) of very large numbers. We can use this to secure credit cards which we use to pay our bills. How does this work? Any one trying to sneak in and steal your credit card information would need to factor very large numbers! That takes time, so the information is secure! This is the basis of the RSA cryptosystem of Ronald Rivest, Adi Shamir and Leonard Adleman.
Checking versus solving
What if we are not trying to solve a problem, but merely checking that someone presenting a solution isn't cheating, that it is indeed a correct answer? For instance, if someone gave you a solution to an equation, it is usually easy to check that it is correct. In fact, that should be easier than finding the solution yourself, right? But it is not easy to formally prove this. It has turned out to be such a hard problem that anyone answering this precisely will get a million (US) dollars prize!
Challenges for robotics
You wonder, we asked about robots, but we have been talking only about childish stuff like multiplication and division! Guess what, finding fast algorithms for (all kinds of) multiplication is such a fundamental challenge, researchers are working on them even now. Also, when a robot is walking in a terrain, it uses sensors to process information, summarises them and acts, it is only a collection of such algorithms that act together. Any improvement in the "little algorithms" can be a major breakthrough for robotics.
Understanding the limits of computation, and dealing with hard problems in multiple other ways, is part of work that is done at IMSc. In particular, Professor Saket Saurabh recently got the Shanti Swarup Bhatnagar Award in mathematical sciences, for his work on ways of coping with such computationally hard problems. See the YouTube video of his recent talk (https://www.youtube.com/watch?v=e6gJCvbQbkc) for more about his work.