1985 理查德·卡普

shiyi18

Richard Karp
BIRTH:
January 3, 1935, Boston Massachusetts

EDUCATION:
AB, Harvard 1955; SM Harvard 1956; Ph.D., Harvard 1959, Applied Mathematics; and eight honorary degrees.

EXPERIENCE:
1959-1968 Research Staff Member, IBM Watson Research Center, Yorktown Heights, New York; 1964-1965 Visiting Associate Professor, Electrical Engineering, University of Michigan; 1968-1994 Professor of Computer Science and of Industrial Engineering and Operations Research, University of California, Berkeley; 1973-1975 Associate Chairman for Computer Science, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley; 1980-1994 Professor of Mathematics, University of California, Berkeley; 1985-1986 Co-chair, Program in Computational Complexity, Mathematical Sciences Research Institute, Berkeley; 1988-1995 Research Scientist, International Computer Science Institute, Berkeley, California; 1995-1999 Professor of Computer Science and Adjunct Professor of Molecular Biotechnology, University of Washington; 1999- University Professor, University of California, Berkeley, Computer Science, Mathematics, and Bioengineering; 1999- Research Scientist, International Computer Science Institute, Berkeley, California; 2001-2003 Chair, Board of Governors, Institute for Mathematics and Its Applications; 2001-2004 Founding Chair, Section 34, National Academy of Sciences.


HONORS AND AWARDS:
Lanchester Prize in Operations Research, 1977 (co-winner); Fulkerson Prize in Discrete Mathematics, 1979; Miller Research Professor, Berkeley, 1980-81; Faculty Research Lecturer, Berkeley, 1981-82; Einstein Fellowship and Lady Davis Fellowship, Technion, Haifa, Israel, 1983; ACM Turing Award, 1985; Distinguished Teaching Award, University of California at Berkeley, 1986; Doctor of Science (honoris causa), University of Pennsylvania, 1986; John von Neumann Lecturer, SIAM, 1987; Doctor of Science (honoris causa), Technion, 1989; Class of 1939 Chair, University of California at Berkeley, 1989; ORSA/TIMS von Neumann Theory Prize, 1990; Doctor of Science (honoris causa), University of Massachusetts, 1990; Doctor of Humane Letters (honoris causa), Georgetown University, 1992; Babbage Prize, 9th International Parallel Processing Symposium 1995; National Medal of Science, 1996; Centennial Medal, Harvard University, 1997; Kyoto Prize, 2008; Harvey Prize; Benjamin Franklin Medal.


RICHARD ("DICK") MANNING KARP DL Author Profile link
United States – 1985
CITATION
For his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness. Karp introduced the now standard methodology for proving problems to be NP-complete which has led to the identification of many theoretical and practical problems as being computationally difficult.

SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE
RESEARCH
SUBJECTS
VIDEO INTERVIEW
Richard Karp was born in Boston, Massachusetts on January 3, 1935. He attended Boston Latin School, and received the A.B, S.M. and Ph.D. degrees in Mathematics and Applied Mathematics from Harvard University in 1955, 1956 and 1959.

Karp then joined the research staff of the IBM Watson Research Center in Yorktown Heights, NY, where he worked until 1968. During that time, Karp did foundational work on models of parallel computation, which involves the simultaneous use of multiple coordinated computers to solve a single problem. Roughly twenty years later, he returned to the study of parallel computation and continues to work in that area.

Karp discusses his nine years at IBM’s Watson Research Center and the work he did there on algorithm design and the mathematics of vector addition systems.       
Motivated by the desire to teach and "to be where the action is," in 1968 Karp moved to the University of California, Berkeley, with appointments in Computer Science and in Operations Research. His dedication to teaching won him the UC Berkeley Distinguished Teaching Award in 1986.

Karp's initial research at Berkeley focused on heuristic algorithms for hard combinatorial problems, particularly for the notoriously difficult Traveling Salesmen Problem (TSP). Like many combinatorial problems, there was no efficient TSP algorithm that could be proved correct for all input, and whose worst-case running time is bounded by a polynomial function of the input size. Also lacking was an explanation of why an efficient algorithm had been so elusive.

Karp explains the difference between P (polynomial time) and NP (nondeterministic polynomial time) algorithmic complexity classes.       
In one of the most significant paper of his career, Karp's 1972 Reducibility Among Combinatorial Problems provided a convincing explanation for the elusiveness of an efficient solution. In that seminal paper, Karp expanded on the concept (first introduced by Stephen Cook in 1971, and independently by Leonid Levin) of NP-completeness and proved that if any of twenty-one well-known difficult problems (including TSP) could be solved by an efficient algorithm, then all of the problems could be efficiently solved.  NP-completeness shows, in an important sense, that these 21 problems are all equivalent. The collective failure by many talented people to find efficient algorithms for specific NP-complete problems strongly suggests that no efficient algorithm exists for any of them. Importantly, the paper established a framework for adding additional problems to the class of NP-complete problems, which has since grown to include many thousands. Today, only one or two classic combinatorial problems remain unclassified as to whether they are NP-complete or not. While most of the classified classic problems are NP-complete, several have been shown to be efficiently solvable.

Karp recounts his formulation of the P=NP question while writing the paper “Reducibility Among Combinatorial Problems” (1972).       
Karp's work on NP-completeness substantially motivated the discussion  of the famous unsolved P = NP question and its further examination by mathematicians and computer scientists. In essence, P = NP asks whether finding a solution to a problem is inherently more difficult than verifying that a proposed solution is correct. Not only is the problem considered the most important open question in theoretical computer science, it is also one of the most important open questions in mathematics.

The year after his paper on NP-completeness, Karp co-authored with Jack Edmonds and John Hopcroft (himself a Turing Award recipient) two very significant papers on efficient algorithms for network flow and bipartite graph matching. The network flow problem is to compute the maximum steady-state amount of material (for example, liquids in a pipe or bits in a communication network) that can be transported from a source to a destination in a network, where each edge (pipe, wire, road etc.) in the network can have a different but bounded capacity. This is one of the most widely studied problems in optimization and algorithmic computer science, and is not limited to physical networks as the same problems arise in, for example, biological cycles. The bipartite matching problem is a particularly useful special case of network flow that has a huge number of non-physical applications. Karp and Hopcroft showed in 1973 that the bipartite matching problem can be solved more efficiently than the general network flow problem [4] .

Another major theme in Karp's research has been the use of probability in both the design and analysis of efficient algorithms. Karp's interest in the probabilistic analysis of algorithms began in the 1980s, when he examined questions of the average, rather than the worst-case, running times of particular algorithms. In probabilistic analysis, the algorithm is fixed and deterministic, but its input is assumed to be drawn from a space universe of possible inputs according to a well-specified probabilistic model. The analysis finds the expected running time (or other characteristic) for that distribution of inputs. Karp later became active in the design of randomized algorithms, where the algorithm itself, rather than the input to the algorithm, has a random component. Surprisingly, randomizing the behavior of an algorithm can often significantly reduce its expected running time for any input.

Karp describes his work on the probabilistic analysis of algorithms, focusing on average rather than worst-case complexity.       
Karp's most recent research has been in computational biology. This work began in the 1990s, as the field began to grow rapidly under the influence of the Human Genome Project. Karp first examined physical mapping of genes, devising algorithms to help determine the physical location of genes in a genome given the limited indirect experimental information about gene location. Such algorithms were especially important before affordable full DNA sequencing became available. From that beginning, Karp has examined a wide range of algorithmic issues in biology, such as:

determining protein interactions
designing and analyzing methods for gene mapping under different data collection technologies
designing and analyzing methods for problems that arise in population genetics and family pedigree analysis
finding repeating patterns and structures in gene sequences
constructing and analyzing networks that represent biological interactions, such as protein-protein contact, gene regulation, and metabolic pathways.
Much of Karp's work in computational biology uses techniques from combinatorial optimization, but more recently his work has also involved stochastic approaches from the field of machine learning. A new direction for Karp, this recent work on machine learning is related to his continuing interest in the use of probability in the design of algorithms and in the analysis of algorithmic behavior.

Karp describes his mid-career shift to apply his combinatorial expertise in the emerging field of computational biology.       
In 1995 Karp left Berkeley for the Department of Computer Science at the University of Washington, where he was also an Adjunct Professor of Molecular Biotechnology. He returned to Berkeley in 1999 with appointments in Computer Science, Mathematics, and Bioengineering.

In addition, Karp is a Senior Research Scientist at the International Computer Science Institute in Berkeley, and was a principal in the creation of the Institute. Karp is currently a University Professor at the University of California, a prestigious title that has been awarded only thirty-eight times. Other major awards include election to the National Academy of Sciences in 1980, election to the National Academy of Engineering in 1992, the U.S. National Medal of Science in 1996, and the Kyoto Prize in 2008.

During his years at Berkeley and Washington, Karp mentored almost forty Ph.D. students. In addition to his professional accomplishments, Karp is an avid reader and chess player.


B. Simons and D. Gusfield



理查德-卡普
出生地：美国
1935年1月3日，波士顿，马萨诸塞州

学历：1955年哈佛大学学士；1956年哈佛大学硕士；1959年哈佛大学应用数学博士；以及八个荣誉学位


工作经验。
1959-1968年，纽约约克镇高地IBM沃森研究中心研究人员；1964-1965年，密歇根大学电子工程系客座副教授；1968-1994年，加利福尼亚大学伯克利分校计算机科学和工业工程及运筹学教授。1973-1975 加州大学伯克利分校电子工程和计算机科学系计算机科学副主席；1980-1994 加州大学伯克利分校数学教授；1985-1986 伯克利数学科学研究所计算复杂性项目联合主席。1988-1995年，加州伯克利国际计算机科学研究所研究科学家；1995-1999年，华盛顿大学计算机科学教授和分子生物技术兼职教授；1999-加州大学伯克利分校计算机科学、数学和生物工程专业大学教授；1999-加州伯克利国际计算机科学研究所研究科学家；2001-2003年，数学及其应用研究所理事会主席；2001-2004年，国家科学院第34分部创始主席。


荣誉和奖项。
1977年，兰彻斯特运筹学奖（共同获奖）；1979年，福尔克森离散数学奖；1980-81年，伯克利的米勒研究教授；1981-82年，伯克利的教师研究讲师；1983年，以色列海法的Technion的爱因斯坦奖学金和戴维斯夫人奖学金。1985年，ACM图灵奖；1986年，加州大学伯克利分校杰出教学奖；1986年，宾夕法尼亚大学科学博士（荣誉学位）；1987年，SIAM约翰-冯-诺依曼讲师。1989年，Technion科学博士（荣誉）；1989年，加州大学伯克利分校1939级主席；1990年，ORSA/TIMS冯-诺依曼理论奖；1990年，马萨诸塞大学科学博士（荣誉）。1992年，乔治敦大学人文博士（荣誉）；1995年，第九届国际并行处理研讨会巴贝奇奖；1996年，国家科学奖；1997年，哈佛大学百年纪念奖；2008年，京都奖；哈维奖；本杰明-富兰克林奖。


RICHARD ("DICK") MANNING KARP DL作者简介链接
美国 - 1985年
褒奖
由于他对算法理论的持续贡献，包括开发了网络流和其他组合优化问题的有效算法，将多项式时间可计算性与算法效率的直观概念联系起来，以及最引人注目的对NP完备性理论的贡献。卡普引入了现在证明问题为NP-完备性的标准方法，这导致了许多理论和实际问题被确定为计算上的困难。

简短注释
书目
亚马逊图灵奖
讲座
研究
题目
视频采访
理查德-卡普于1935年1月3日出生在马萨诸塞州的波士顿。他就读于波士顿拉丁学校，并于1955年、1956年和1959年在哈佛大学获得数学和应用数学的学士、硕士和博士学位。

卡普随后加入了位于纽约州约克敦高地的IBM沃森研究中心的研究人员，在那里工作到1968年。在此期间，卡普在并行计算的模型方面做了基础性的工作，这涉及到同时使用多台协调的计算机来解决一个问题。大约二十年后，他回到了平行计算的研究，并继续在这个领域工作。

卡普讨论了他在IBM沃森研究中心的九年，以及他在那里做的算法设计和向量加法系统的数学工作。       
出于对教学和 "在行动的地方 "的渴望，卡普于1968年来到加州大学伯克利分校，担任计算机科学和运筹学方面的职务。他对教学的执着为他赢得了1986年的加州大学伯克利分校杰出教学奖。

卡普在伯克利的最初研究集中在困难组合问题的启发式算法上，特别是众所周知的困难旅行推销员问题（TSP）。像许多组合问题一样，没有一种高效的TSP算法可以被证明对所有输入都是正确的，而且其最坏情况下的运行时间被输入大小的多项式函数所限制。同样缺乏的是对高效算法为何如此难以捉摸的解释。

卡普解释了P（多项式时间）和NP（非确定性多项式时间）算法复杂度等级之间的区别。       
在他职业生涯中最重要的论文之一，卡普1972年发表的《组合问题中的可缩减性》为高效解决方案的难以捉摸提供了一个令人信服的解释。在这篇开创性的论文中，卡普扩展了NP-完备性的概念（由斯蒂芬-库克在1971年首次提出，并由列昂尼德-列文独立提出），并证明如果21个著名的难题（包括TSP）中的任何一个可以用有效的算法解决，那么所有的问题都可以被有效解决。 NP完备性在一个重要意义上表明，这21个问题都是等价的。许多有才能的人都没有找到特定的NP完备性问题的有效算法，这强烈地表明其中任何一个问题都不存在有效算法。重要的是，这篇论文建立了一个框架，可以将更多的问题加入到NP-complete问题的类别中，而这个类别后来已经发展到包括成千上万的问题。今天，只有一两个经典的组合问题仍然没有被分类，不知道它们是否是NP-complete。虽然大多数被分类的经典问题都是NP不完全的，但有几个问题已经被证明是可以有效解决的。

卡普在写《组合问题中的可减少性》（1972）一文时讲述了他对P=NP问题的表述。       
卡普关于NP完备性的工作极大地推动了对著名的未解决的P=NP问题的讨论以及数学家和计算机科学家对它的进一步研究。从本质上讲，P=NP问的是找到一个问题的解决方案是否比验证一个提议的解决方案是否正确本身就更困难。这个问题不仅被认为是理论计算机科学中最重要的开放问题，也是数学中最重要的开放问题之一。

在他关于NP完备性的论文发表后的第二年，卡普与杰克-埃德蒙兹和约翰-霍普克罗夫特（他本人也是图灵奖获得者）共同发表了两篇非常重要的论文，内容是关于网络流和双比特图匹配的高效算法。网络流量问题是计算在一个网络中从源头到目的地可以运输的最大稳态物质数量（例如，管道中的液体或通信网络中的比特），其中网络中的每条边（管道、电线、道路等）可以有不同但有限制的容量。这是优化和算法计算机科学中研究最广泛的问题之一，并不限于物理网络，因为同样的问题出现在例如生物循环中。双边匹配问题是网络流的一个特别有用的特例，有大量的非物理应用。Karp和Hopcroft在1973年表明，双点匹配问题可以比一般的网络流问题得到更有效的解决 [4] 。

Karp研究的另一个主要主题是在高效算法的设计和分析中使用概率。卡普对算法的概率分析的兴趣始于20世纪80年代，当时他研究了特定算法的平均运行时间，而不是最坏情况下的运行时间问题。在概率分析中，算法是固定的和确定的，但它的输入被假设为根据一个明确的概率模型从可能的输入空间宇宙中抽取。分析发现该输入分布的预期运行时间（或其他特征）。卡普后来开始活跃于随机算法的设计中，其中算法本身，而不是算法的输入，具有随机成分。令人惊讶的是，随机化算法的行为往往可以大大减少其对任何输入的预期运行时间。

卡普介绍了他在算法的概率分析方面的工作，重点是平均复杂度而不是最坏情况下的复杂度。       
卡普最近的研究是在计算生物学方面。这项工作开始于20世纪90年代，因为该领域在人类基因组计划的影响下开始迅速发展。卡普首先研究了基因的物理图谱，设计了一些算法来帮助确定基因在基因组中的物理位置，因为关于基因位置的间接实验信息有限。在可负担得起的全部DNA测序技术出现之前，这种算法特别重要。从这个开始，卡普研究了生物学中广泛的算法问题，例如。

确定蛋白质的相互作用
设计和分析不同数据收集技术下的基因图谱方法
为人口遗传学和家族血统分析中出现的问题设计和分析方法
寻找基因序列中的重复模式和结构
构建和分析代表生物相互作用的网络，如蛋白质-蛋白质接触、基因调节和代谢途径。
卡普在计算生物学方面的大部分工作都使用了组合优化的技术，但最近他的工作也涉及机器学习领域的随机方法。对卡普来说，最近关于机器学习的工作是一个新的方向，这与他对在算法设计和算法行为分析中使用概率的持续兴趣有关。

卡普描述了他在职业生涯中期的转变，将他的组合学专业知识应用于新兴的计算生物学领域。       
1995年，卡普离开伯克利到华盛顿大学计算机科学系工作，同时也是分子生物技术的兼职教授。1999年，他回到伯克利，在计算机科学、数学和生物工程领域任职。

此外，卡普是伯克利国际计算机科学研究所的高级研究科学家，也是创建该研究所的负责人。卡普目前是加州大学的大学教授，这个著名的头衔只颁发过三十八次。其他主要奖项包括1980年当选为国家科学院院士，1992年当选为国家工程院院士，1996年获得美国国家科学奖，2008年获得京都奖。

在伯克利和华盛顿的几年里，卡普指导了近四十名博士生。除了他的专业成就外，卡普还是一个狂热的读者和国际象棋选手。


B. 西蒙斯和D.古斯菲尔德