Over Head Transmission

When I read this on Varnam, I reached here. Then when I read some other posts on Rahul Siddharathan's blog, of which I understood very little, a question came up in my mind

What is computational lingusitics?

This question led me here. From here, I came to know that one of the fields of research in computational lingusitics is Computational Complexity. This led me to theory of computation, which is ofcourse the background of all the computer science problem modeling. So I read a little bit about this.

I knew from some general reading and discussions with my friends that P and NP classes in computational theory meant Polynomial time complexity and Nondeterministic Polynomial time complexity respectively but never got any clear understanding of Theory of Computation. This raised the question:

What is Computational Complexity anyway?

So went back to Computational Complexity page on wikipedia. I read a little and got a little idea but I decided that I would need to really take up some books on theory of computation to understand in a better way. However, the point of this post is different.

While reading about Computational Complexity, I also read about AKS primality test. AKS Primality Test is today a very important algorithm in Computational Complexity branch of Theory of Computation.

For the un-initiated, AKS Primality test is the algorithm announced by Dr. Manindra Aggarwal, Neeraj Kayal and Nitin Saxena in the year 2002. The Indian Institute of Technology Kanpur (IITK) computer scientists developed this algorithm whose computational time complexity is defined by an "unconditional deterministic polynomial". Till they wrote this paper, no one knew an algorithm that could work out and tell you if an integer n is Prime, in deterministic amount of time.

This algorithm can tell you if given an integer 'n' is a prime number or not in O(log^(21/2)n) of computational time.

I read in newspapers in 2002 about these guys but never gave a thought about what they had achieved. AKS primality test was a path breaking observation. Lot of people improvised on it later but it was historic paper in the field of Mathematics. The algorithm is today used in scores of applications including crypotgraphic applications which help you safely transfer money from your bank account to your father's account back in your home town.

I cant comment on the paper, given my wafer thin knowledge of theory of computation and computational complexity. When I downloaded it from here and went through it, I was looking my computer with a dropped jaw "ఏంటో ఏమి అర్ధం అవటం లేదు!". I remember using the phrase "Over Head Transmission" during some lectures/reading sessions in Bachelors study especially when studying about Electro magnetics and Aantenna design but I truly understood what OHT is today after reading this paper!