Exascale computer algebra problems interconnect with molecular reactions and complexity theory
Robert Warren Williams, David R. Wood · DIMACS series in discrete mathematics and theoretical computer science · 1998
In discussing exascale (exa = 10 18 ) computer algebra problems we interconnect three themes. First, DNA is an attractive medium for computation because of its density and parallelism. Second, computer algebra is similar to DNA laboratory reactions. Both rearrange identical subunits. Third, determinant and/or permanent expansions exemplify many levels of complexity. These three issues are combined in a planned experiment using a DNA algorithm to evaluate or approximate the permanent of a matrix of zeros and ones, a well-known problem in the class #P-Complete. Such problems are harder than those previously addressed by DNA techniques in the pioneering articles of Adleman and Lipton. This points the way to DNA methods for expanding a symbolic determinant given its zero pattern, which is of still higher complexity. We begin to approach interesting problem sizes because we reduce scale-up difficulties by alternating intermediate steps of building and filtering. The example algo...