P != NP

04 Nov 2011

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.