P != NP

If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss… — Scott Aaronson

“…And hence P!=NP. QED”, wrote Ryan Brown. He could not believe his eyes. He had finally done it. The efforts of the past 23 years of his life had finally yielded fruit. He had proven the greatest mathematical problem of them all.

As an undergraduate student at MIT in 2011, Ryan came across the problem in his algorithms course. He was fascinated by how such a seemingly straighforward problem had stumped computer scientists for ages. It seemed obvious that you would have to try out all possible combinations in the 3-SAT problem to solve it. Or did it? He dwelled upon the problem, obsessed about it. Finally he decided that he could not be happy doing anything else. Ryan Brown would solve the P-NP problem, and would dedicate his whole life to it, if need be.

As he went from publisher to publisher, his despair grew. At first, he was confident that any journal would be glad, even honoured to publish this momentous result. Imagine his surprise, then, when he was politely declined by not one, but seven consecutive journals. As he went to the eighth publisher, his confidence in the result of the meeting was considerably lower than when he went to the first one. “…And hence, I proved this momentous result.”, Ryan explained to the publisher. The publisher listened patiently, but with a smug look on his face, as if he had already made up a decision. “But what use is it?”, he asked as Ryan finished his monologue. 

The third world war between USA and China broke out in 2018. Nobody could say that they did not expect it. That it wasn’t unexpected did not mean it wasn’t unpleasant, though. For Ryan, it meant that his research would have to halt, or at least slow down. He could not avoid conscription, as his research did not directly benefit the military. He was posted in South America, where he served for 9 months, till he was shot in the leg, and was allowed to return. His passion undeterred, he continued his research as before. However, the war had significantly changed the world’s outlook on research. There was a great degree of pragmatism that had crept into the mindset of the authorities and the researchers alike. Research in theoretical areas and mathematics was dismissed as mere mental amusement, and not deemed worthy of significant efforts or funding. Engineering, which could make missiles, radars and tanks that gave immediate tactical advantage in the war, received hefty funding and approval. Even when the war ended, the attitudes persisted. Ryan’s funding had dropped to a trickle. However, all he needed for his work was access to his books, papers, a blackboard, and his mind – all of which was intact.

“Fine, I’ll publish it”, said the thirteenth publisher Ryan approached, “Don’t expect me to pay you any royalties upfront, though. I doubt if this will earn me anything.” At that point of time Ryan was ready to accept anything – anything to get his idea out into the open, to let the world know that he had done what mathematicians had been struggling with for over 60 years!

“…And hence P!=NP. QED”, wrote Ryan Brown. He could not believe his eyes. He had finally done it. The efforts of the past 23 years of his life had finally yielded fruit. He had proven the greatest mathematical problem of them all.

Ryan Brown’s seminal paper turned out to be not so seminal after all. It didn’t really change the world view at all. Turned out that everyone who could appreciate a symphony was not Mozart after all. Ryan Brown died in 2035, a year after finishing his life’s work.

The world carried on as usual.

Non Euclidean Geometries

I wrote a few articles on Mathematics for a magazine for school kids, EducationEdge. These articles are targeted at students of classes VIII to XII. Am reproducing one of them here, hoping some of the readers of this blog might enjoy it too. 

Introduction

Science seeks to figure out how the Universe works, and tries to discover the laws which govern it. Mathematics has no such obligations. Though mathematicians and their theories generally stick to the Universe that we live in, once in a blue moon there will rise an eccentric, but genius mathematician, who will propose a radical mathematical theory, which though marvelous, has seemingly no application – at least not in this universe. In this article, we shall talk about Non-Euclidean Geometry, which is literally out-of-this-world Mathematics.

What is Geometry?

Since we have all studied some geometry in school, we have generally some intuitive idea about what lines, points, circles and planes are. The ancient Greek mathematician Euclid showed that all our intuitive notion about geometric objects can be summarized into a set of five postulates. If these postulates are assumed to be true, all the rest of geometry follows. Hence, the next time your teacher tells you to memorize some rules about circles or parallel lines, you can refuse to do so, saying that you already know Euclid’s postulates. (Disclaimer: The author is not responsible for what your teacher does to you after this!!). Euclid’s postulates are as follows:

  1. A straight line can be drawn that connects two given points
  2. A line segment can be extended in both directions to get a straight line
  3. A circle with a given center and radius can be drawn
  4. All right angles are equal to each other
  5. Given a line and a point not lying on it, exactly one line can be drawn that passes through the given point and is parallel to the given line.

Non-Euclidean Geometry

As you can see, the postulates seem simple and obviously true. However, mathematicians are not simple and obvious creatures. A few mischievous mathematicians thought, “What if we assume one of these postulates to be false? What if we assume something that is contrary to one of these postulates to be true?” They did so, and came up with several different kinds of geometries, all of which are inconsistent with our normal notion of Geometry, but nonetheless, consistent within themselves. “But what is the use of all this?”, you may ask, “If these geometries are not real, and don’t work in our Universe at all, why do mathematicians want to study them?” These are very valid questions, but mathematicians are a crazy bunch of people, and often do mathematics just for the sake of it, even if it seems to have absolutely no utility anywhere in the real world.

Elliptical Geometry

One of the non-Euclidean geometries, that is relatively easy to understand is called Elliptical Geometry. In this geometry, the fifth postulate in Euclid’s postulates is changed.

  • Given a line and a point not lying on it, no line can be drawn that passes through the given point and is parallel to the given line.

In order to understand this, you must suspend your usual notions about what a point, line, etc are. In our new universe, these are entirely different things than what we usually think of them. We shall hence redefine them in our new universe. To avoid confusion, we shall write point when we wish to refer to constructs in the new universe, and point when we wish to refer to our usual notion. Imagine a sphere. A plane is defined as the surface of this sphere. A point is defined as a pair of diametrically opposite points on this sphere. A line is a great circle on the sphere(A great circle is a circle, like the equator, whose plane contains the center of the sphere). Notice that two lines always intersect in exactly two diametrically opposite points, that is exactly one point.

Observe that in this elliptical geometry, the first four of Euclid’s postulates still hold. (Keep down this article and think about the first two postulates now. I assure you that you will find it a rewarding exercise). Though we have not formally defined circles and angles due to lack of space, it can be proved that the third and fourth postulates also hold true in elliptical geometry. Notice also, that the new fifth postulate is now true in this system. Given a line and a point lying outside it, it is impossible to construct a line parallel to the one given. Remember that a line must lie on the plane and since, in this case a plane is the surface of the sphere, the plane of any line through a given point must pass through the centre of the sphere and thus must intersect the given line at some point (see Figure). This makes it impossible, in Elliptical Geometry, to draw a pair of parallel lines! Many other interesting and non-intuitive facts also emerge in this system. For example, the sum of the angles of a triangle is greater than 180 degrees. Mindboggling, but true.

Conclusion

We saw that even a simple subject like geometry is a subject of deep mathematical study. The essence of mathematics is to question. Mathematicians ask questions like, “What is a number?” or “What is a point?” Though they seem silly, finding the answers to these questions involves much thought, and a journey full of adventure into the dark and mysterious land of mathematics.