UB Researchers Use Randomization to Prove A Conjecture In Complexity Theory

BUFFALO, N.Y. -- University at Buffalo computer scientist Jin-Yi Cai and a computer science graduate student, D. Sivakumar, have proven one of the oldest conjectures in the field of complexity theory.

They did it using a combination of mathematical techniques, including an algebraic tool called finite field theory, randomization and parallel computation. The researchers noted that based on the information contained in the conjecture, the success of this multifaceted approach was extremely unexpected.

Paradoxically, Cai said, the proof is an example of a case where randomization, one of the complexity theorist's most powerful tools, can be extremely effective, but is ultimately supplanted by other mathematical tools.

The research will be presented Tuesday, Oct. 24 in Milwaukee at the Annual Symposium of Foundations of Computer Science, one of the most important computer science conferences, sponsored by the Institute of Electrical and Electronics Engineers.

The conjecture the proof settled was proposed in 1978 by Juris Hartmanis of Cornell University, who won the Turing Award, the most prestigious prize in computer science research, for his own work in complexity theory.

The conjecture concerns the relationship between problems that can be solved in polynomial time (that is, in a reasonable amount of time) and those that can be solved using an exceedingly small amount of space (as in disk space).

The solution to it depends heavily and, Cai said, unexpectedly, on finite field theory.

That theory was written in 1832 by the ill-fated French mathematician, Evariste Galois, on the very night he was killed in a duel over the woman he loved. Discovered years later, his theory has turned out to have had an extremely profound impact on the entire development of mathematics ever since, most recently in complexity theory.

"In our proof, we start with randomization but then use finite field theory to create an illusion of randomization, and yet ultimately it is not random," Cai said. "Without

randomization, we probably wouldn't have obtained the proof. On the other hand, by the end of the proof, randomization is supplanted by a deeper understanding of the problem."

Cai said that the interesting role of randomization in this proof underscores its role in complexity theory in general.

"In this proof, you could say that because it was eliminated in the end, it was just a detour," said Cai. "Or, you could see it as a shortcut, without which we couldn't have solved it. The beauty of randomization is that it might be applicable to problems that seem not to have anything to do with randomization."

The proof, which took several months of intensive research to complete, extends the work of Mitsunori Ogihara of the University of Rochester, who announced important findings on the conjecture earlier this year.

"I congratulate these researchers on a new insight in the relations between computation time and memory requirements for polynomial time computations," said Hartmanis. "I am delighted that this conjecture, posed by me in 1978 has been solved."