伦纳德·阿德尔曼

伦纳德·阿德尔曼（Leonard Adleman）1945年出生于美国旧金山，1968年毕业于加州大学伯克利分校，1976年在该校完成计算机科学博士学位。他的博士研究涉及计算复杂性的数论问题，随后赴麻省理工学院任教，1980年转到南加州大学。

阿德尔曼的职业经历连接了几种不同的计算问题：数学运算何时容易或困难，如何利用这种差异保护信息，以及计算能否在电子电路以外的介质中实现。他与罗纳德·里维斯特、阿迪·沙米尔共同获得2002年度图灵奖，而DNA计算则是其另一条独立研究方向。

参考：[1]

在麻省理工学院，阿德尔曼与里维斯特、沙米尔合作研究公开密钥密码。1978年共同发表的RSA论文给出具体的加密和数字签名方法：公开两个大素数的乘积及相应指数，同时保留可完成反向运算的秘密信息。RSA名称中的A指阿德尔曼，但缩写不是用来排列三人贡献大小的证据。

该构造使发信人可以使用公开信息加密，而不必先与收信人分享同一个加密秘密。若攻击者能分解公开模数，便可恢复关键的秘密参数；这解释了整数分解为何与RSA密切相关。它并没有把“某种数学任务看起来困难”直接变成无条件安全证明，也没有证明所有求解方式都必然等价于整数分解。

参考：[2]

1994年，阿德尔曼发表DNA计算实验，处理一个七顶点有向图的哈密顿路径问题：从指定起点出发，到指定终点结束，并且每个顶点恰好经过一次。顶点和有向边由DNA短链编码，互补配对及连接反应产生代表许多候选路径的分子。

后续操作不是直接让试管“知道答案”，而是逐步筛选。实验先保留起终点符合要求的路径，再按长度保留经过七个顶点的候选，随后筛出包含各个顶点的分子。长度约束与覆盖全部顶点的约束结合，排除了重复经过顶点而遗漏其他顶点的路径；最后检测剩余产物。

参考：[3]

这一小图的答案可以直接观察得到，实验的重要性因此不在于胜过电子计算机，而在于用分子操作实际实现一套计算步骤。论文同时指出，候选分子的数量需求会随图的顶点数呈指数增长；操作步骤看似不多，并不意味着总资源也只作线性增长。

规模扩大还会带来错误连接、分离不完全和结果核验等问题。大量分子同时参与反应提供了并行性，却不能由此断言所有NP难题都得到通用高效解法。阿德尔曼的贡献，是把计算理论中的编码、搜索与验证带入实验介质，同时让其资源代价成为可以讨论和检验的问题。

参考：[3]