Stephen Cook

Stephen Cook
University of Toronto

The P vs NP Problem and its Place in Complexity Theory
 
Abstract: We present an historical treatment of the P vs NP problems, and discuss its importance and approaches for solving it. We relate it to the satifiability problem and the field of proof complexity.

Quick Links

2012-2013 DLS

  • Zvi Galil
  • Hector Levesque
  • Jennifer Chayes
  • Renée Miller
  • Maneesh Agrawala
  • David Eppstein

2011-2012 DLS

  • Bruno Buchberger
  • Saul Greenberg
  • Ed Lazowska
  • Jeannette Wing
  • Cynthia Dwork

2010-2011 DLS

  • Stuart Feldman
  • Madhu Sudan
  • Susan Landau
  • Gilles Brassard
  • Joe Marks
  • Jon Kleinberg

2009-2010 DLS

  • Andy Yao
  • Paul Van Oorschot
  • Shafi Goldwasser
  • Adi Shamir
  • Fran Allen

2008-2009 DLS

  • Alan Kay
  • Eric Brewer
  • Anne Condon
  • Nancy Leveson
  • Tom Furness

2007-2008 DLS

  • David Patterson
  • Manuela Veloso
  • David D. Clark
  • Christos Papadimitriou

2006-2007 DLS

  • Kurt Mehlhorn
  • Ben Shneiderman
  • Barbara Liskov
  • Vint Cerf

2005-2006 DLS

  • Umesh Vazirani
  • Stephen Cook
  • Andrew Tanenbaum
  • Andries van Dam

2004-2005 DLS

  • Alfred Aho
  • Brian Kernighan
  • Jim Gray
  • Barbara Grosz
  • Jim Mitchell