Mathematical Digest

Short Summaries of Articles about Mathematics
in the Popular Press

"Successes and Challenges," by John H. Reif. Science, 19 April 2002, pages 478-9.

Reif writes about the recent solution of a 20-variable satisfiability problem using DNA computing. Satisfiability refers to finding what truth values, if any, can be assigned to Boolean variables so that a given Boolean formula is true. Such problems are known to be NP-hard and so make good tests for computing. Since the number of DNA strands needed to solve a problem grows exponentially with the size of the problem, DNA computing is not unlimited in its scope--Reif points out that the limit for the satisfiability problem is no more than 80 Boolean variables. The research article giving details about the solution of the problem, "Solution of a 20-Variable Problem on a DNA Computer," is on pages 499-502 of the same issue.

--- Mike Breen