RICHARD KARP

PRIX TURING 1985
BIO
PAGE
COMPLEXITE
NP
P=NP


Pour ses contributions continues à la théorie des algorithmes, notamment le développement d'algorithmes efficaces pour les réseaux et d'autres problèmes d'optimisation combinatoires, l'identification de calculabilité en temps polynomial avec la notion intuitive d'algorithme efficace, et surtout, ses contributions à la théorie de la NP-complétude. Karp a introduit la méthodologie désormais classique pour prouver qu'un problème est NP-complet, ce qui a permis d'identifier de nombreux problèmes pratiques et théoriques comme étant difficiles à calculer.


1935

Richard Karp est né à Boston, le Massachusetts en 1935 et a été instruit à l'école de Boston Larin et à l'université de Harvard, où il a reçu un Ph.D. dans des mathématiques appliquées en 1959. Sa dissertation a été basée sur l'idée que l'écoulement de la commande dans un programme machine peut être représenté par un graphique dirigé, et que des algorithmes de théorie de graphique peuvent être employés pour analyser des programmes. Après ceci, il a travaillé pour le département mathématique des sciences au centre de recherches d'IBM Thomas J. Watson, où il a travaillé jusqu'en 1968.
Il a travaillé en tant que professeur de l'informatique, des mathématiques et de la recherche opérationnelle de 1968 à 1994 à l'université de la Californie, Berkeley. Karp a conduit la recherche principale et a écrit plusieurs articles dans le domaine du calcul parallèle. Il s'est concentré sur le rôle du randomization dans la construction des algorithmes parallèles efficaces, la preuve des limites inférieures sur la complexité du calcul parallèle, et l'identification que la communication est la ressource essentielle dans la plupart des applications du traitement parallèle. Il a reçu la médaille nationale des ETATS-UNIS de la Science et de la récompense de Turing algana

Les années 1960—1970 voient également l’émergence d’une théorie de la complexité, domaine qui s’inspire d’une abstraction de la complexité des algorithmes et puise ses racines dans la théorie de la calculabilité examinée ci-dessous. L’optimisation combinatoire, issue pour une large part du traitement informatique de problèmes de recherche opérationnelle, effectue une jonction avec la théorie de la complexité grâce aux travaux de Stephen Cook et Richard Karp vers 1970. Ceux-ci montrent en effet que parmi des centaines de problèmes d’optimisation discrète qui étaient l’objet de recherches éparses, il existe une classification fondamentale: d’une part la classe P de ce qui est résoluble en temps polynomial en la taille des données; d’autre part la classe NP des problèmes dont une solution est facilement vérifiable mais difficilement trouvable (l’aiguille dans une botte de foin!). Cette trame imprègne désormais l’ensemble de l’informatique; elle donne à son tour lieu à l’émergence de nouvelles méthodes conçues pour contourner les barrières de complexité de la classe NP: techniques d’approximation, approches probabilistes, raffinements « paramétrés » en sont des exemples. Notons que le problème P =? NP est l’un des sept « Problèmes du Millénaire » recensés en sciences mathématiques par la Fondation Clay.


À partir de 1976, Michael O. Rabin découvre et popularise l’importance d’approches probabilistes dans la conception d’algorithmes. C’est ce qu’on appelle parfois l’aléatoirisation (randomisation, en anglais) —l’aléa est introduit volontairement dans le calcul. L’ordinateur peut avoir intérêt à jouer aux dés… Ce changement de paradigme de programmation apporte dans un nombre de domaines des gains spectaculaires. Il s’agit notamment des calculs arithmétiques, des structures de données classiques pour l’accès rapide à l’information, de la géométrie algorithmique, et de l’algorithmique distribuée. Ainsi une algorithmique probabiliste permet pour la première fois de déterminer la primalité (avec risque d’erreur inférieur à 10-100) de nombres de plusieurs centaines de chiffres : le système cryptographique RSA qui garantit quotidiennement la sécurité de plusieurs millions de transactions repose sur ces techniques. Dans un autre domaine, afin que des ordinateurs communiquent en réseau, il est avantageux de se départir de l’approche déterministe de la téléphonie classique et de résoudre les conflits d’accès tout simplement par tirages au sort: ces principes sont à la base des réseaux Ethernet et du protocole TCP régissant plus de 90% des échanges sur l’Internet.


Pour les trois grandes catégories de problèmes cités, il est clair qu’une démarche mathématique joue tout d’abord un rôle capital dans la formalisation des problèmes et la constitution d’un cadre de pensée. La recherche en optimisation combinatoire n’est plus la même —elle est infiniment plus structurée et fructueuse— après les travaux de Cook, Karp, et leurs successeurs. Les percées de Knuth et Rabin, relayées par une large part de la communauté des chercheurs informaticiens, ont changé la manière dont se conduit la recherche en algorithmique,en offrant des repères clairs dans ce qui ne serait autrement qu’une jungle de techniques. Les sciences mathématiques alimentent continûment l’algorithmique, en suscitant les principes de nouveaux algorithmes ou encore en permettant, via l’analyse d’algorithmes,les optimisations et dimensionnements fins qui sont nécessaires à de nombreuses applications informatiques.pauillac inria


La question « P = NP ? » est l'un de sept problèmes sélectionnés par l'Institut Clay en l'an 2000 : comme pour les six autres, une somme d'un million de dollars attend celle, celui ou ceux qui le résoudront. Certains affirment que c'est le plus important des sept problèmes et donc la principale énigme des mathématiques d’aujourd'hui. Il semble aussi être le seul dont la résolution aurait des conséquences pratiques (il est lié à des centaines d’énoncés concrets) et sa portée philosophique est la plus grande : la question « P = NP ? » concerne la nature de la recherche de solution(s) dans un ensemble exponentiel de possibilités, ce qui est le problème même de la recherche scientifique.

En revanche, la résolution de ce problème peut également avoir un impact négatif sur l’informatique, notamment en cryptographie où beaucoup d’algorithmes de cryptage deviendraient facilement « crackable » et par conséquent inutiles. probleme p np