Math in the Media

Also see the Blog on Math Blogs

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