NP or Not NP

That is the question.  While many problems in computer science have been classified as P or NP-complete problems there is a whole other group of problems that computer scientists haven’t been able to place into each category yet.  Once such problem is known as the “graph isomorphism” problem.  This question posed in this problem is whether two networks that look different are actually the same.  In class we talked about the significance of the P vs. NP question.  While this problem does not have quite the same widespread impact, it had been an open problem in computer science for quite some time now.

The previous best solution for this problem was introduced in 1983. But, in December 2015 professor Laszlo Babai, of the University of Chicago, introduced a new solution that was more efficient than the previous one.  He proceeded to later retract his claim after a flaw in his algorithm was pointed out, but on January 9th, 2017 he announced that he had fixed the error and reintroduced his algorithm.  Both his solution and the previous best one exist in the odd space between P and NP-complete problems.  The previous solution having a complexity classified as “subexponential” and Babai’s new solution being classified.  The question of how to classify the graph isomorphism remains open but as more efficient algorithms continue to be found, many computer scientists are of the opinion that it will eventually be found that it belongs in P.

So what is the significance of this result?  Well a very important distinction needs to be made.  Graph isomorphism is know to be an NP problem but it is not know whether it is NP-complete.  Therefore even if a polynomial solution is found, it has no significant effect on the P vs. NP question, at least for now.  This doesn’t make it is totally insignificant though.  This problem does have the property of being a universal one.  This means that any problem asking whether two “combinatorial structures” are isomorphic can be somehow thought of as a graph isomorphism problem.  One such example is the question of whether two sudoku puzzles are the same.  It may not lead directly to discovering a factorization algorithm that runs in polynomial time but it is certainly an exciting result in the field of computer science.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s