As a mathematician, Putnam contributed to the resolution of Hilbert's tenth problem in mathematics. Yuri Matiyasevich had formulated a theorem involving the use of Fibonacci numbers in 1970, which was designed to answer the question of whether there is a general algorithm that can decide whether a given system of Diophantine equations (polynomials with integer coefficients) has a solution among the integers. Putnam, working with Martin Davis and Julia Robinson, demonstrated that Matiyasevich's theorem was sufficient to prove that no such general algorithm can exist. It was therefore shown that David Hilbert's famous tenth problem has no solution.
In computer science, Putnam is known for the Davis-Putnam algorithm for the Boolean satisfiability problem (SAT), developed with Martin Davis in 1960. The algorithm finds if there is a set of true or false values that satisfies a given Boolean expression so that the entire expression becomes true. In 1962, they further refined the algorithm with the help of George Logemann and Donald W. Loveland. It became known as the DPLL algorithm. This algorithm is efficient and still forms the basis of most complete SAT solvers.
No comments:
Post a Comment