Using complexity theory, they recently randomly generated a test using high-precision division arithmetic that pinpointed the flaw in the Pentium computer chip.

Jin-Yi Cai, UB associate professor of computer science, said that prototype benchmarks using complexity theory that he developed with his colleagues and students, have the potential to test computer hardware for a range of variables, including processor speed and memory capacity.

"The purpose of a benchmark is to verify a manufacturer's performance claims about the speed and accuracy of a specific product," Cai explained.

Problems may get past design teams, he noted, because current benchmarks are not rigorous or objective enough. By subjecting products to a problem with a specified complexity, Cai said, manufacturers could prevent or correct design flaws before they hit the market.

What's missing from the current generation of benchmarks, Cai believes, is an objective criteria and a certain amount of randomness in generating the actual test that will provide a realistic assessment of how a product will perform under the most demanding and unpredictable computational conditions.

Cai and Richard J. Lipton, computer science professor at Princeton University and co-investigator on a National Science Foundation grant, say that a benchmark based in computational complexity would be more accurate because it would safeguard against "loopholes" in current benchmarks that allow some errors to go undetected.

If a benchmark is generated that has a certain specified computational complexity, then a manufacturer who can pass the test in a certain amount of time essentially proves his performance claim.

Cai said that he and his colleagues could generate an objective benchmark based on computational complexity and a certain amount of randomness that certifies the objectivity of test results of many computer products by any manufacturer.

Cai has been awarded the prestigious Alfred P. Sloan Fellowship and a Presidential Young Investigator Award for his work in complexity theory.