Story of the Week  
The Complexity of Some Isomorphism Problems
 

One of the fundamental objectives of Computer Science is to solve problems using computers that are very difficult and/or cumbersome to solve otherwise. For example: computing an approximate solution of a complex differential equation. Naturally, one would like to solve such problems on computers as quickly as possible. This has given rise to the fields of algorithms and complexity theory. The field of algorithms concerns itself with trying to solve a given problem as quickly as possible while that of complexity theory tries to come up with arguments showing why a certain problem cannot be solved more efficiently than the currently known method. For a problem, when both the fields converge, one gets an optimal method for solving the problem.

Mathematics has proved to be a rich source of problems for Computer Science. It has provided basic problems like implementing addition, multiplication of numbers to complex problems like computing Fourier transform, solving differential equations, polynomial factorization etc.
Many of these problems are used in a wide variety of applications, e.g., storing images in JPEG format, storing songs in MP3 format, error-free and secure transmission of data etc.

In this writeup, three problems from mathematics are discussed: Graph Isomorphism, F-Algebra Isomorphism, and Cubic Form Equivalence. The Graph Isomorphism problem is as follows. We are given two undirected simple graphs over n vertices, say G and H. The vertices in both the graphs are numbered from 1 to n. The problem is to decide if the two graphs are isomorphic. In other words, to check if renumbering the vertices of G make it equal to H. This problem has had a long history.
It is useful in several places, for example in classifying the structure of large molecules (the atoms are "vertices" and bonds between them are "edges"). It is known that this problem is unlikely to be NP-hard and so the problem might be easy to solve. At the same time, no efficient algorithm is known for solving the problem.

The F-Algebra Isomorphism problem is as follows. Given two algebras over field F (algebras are commutative rings with identity), test if they are isomorphic. This is one of the basic problems in mathematics. When the two algebras are fields, it is easy to test the isomorphism. However, in general, the problem is not easy to solve. When F is an algebraically closed field (for example, the field of complex numbers), then -- using the famous Hilbert's Nullstellensatz -- one can show that the problem can be solved within polynomial space. When F is the field of reals, then -- using another famous result by Tartski on decidability of first-order theory of reals -- one can show that the problem can be solved in doubly exponential time. When F is the field of rational numbers, the status of the problem is open -- it is not even known to be decidable! When F is a finite field, its complexity is very similar to that of Graph Isomorphism.

The Cubic Form Equivalence problem is as follows. Given two homogeneous, degree three polynomials over field F, test if the first one becomes equal to the second one under a linear transformation. This problem is also very well studied in mathematics. In case of degree two polynomials (instead of degree three), the problem has a very elegant and efficient solution for any F. However, degree three case does not appear so easy.
The complexity of the problem also depends on the field F and behaves in the same way as the complexity of the F-Algebra Isomorphism problem.

Interestingly, although these three problems do not seem related to each other, it can be shown that, in fact, they are! The Graph Isomorphism problem can be transformed to F-Algebra Isomorphism problem which, in turn, can be transformed to Cubic Form Equivalence problem. In addition, the Cubic Form Equivalence problem can be transformed to F-Algebra Isomorphism problem making the two problems equivalent to each other.

These results -- although not shedding much light on the exact complexity of these problems -- exhibit a deep relationship between the three problems and might be useful in future to settle their complexity.

More details about Dr. Manindra Agarwal's work, please visit his website: http://www.cse.iitk.ac.in/users/manindra/

Previous Story

Economical Road Design

Molecular Starbursts

2004 Sumatra Earthquake and Tsunami

The Flow Induced Vibrations

Novel Ceramics

The Complexity of Some Isomorphism Problems

-Flows

Ordered Peptide Aggregation

Asymmetric Synthesis

Optimization