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 was presented 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."

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.