Steve Cook

DIMACS Center - Rutgers University
CoRE Building, 1st Floor Lecture Hall
Piscataway, New Jersey
Monday, March 11, 1996
9:00 AM

Topic of Discussion

FINDING HARD INSTANCES FOR THE SATISFIABILITY PROBLEM

Abstract:

The satisfiability problem is NP complete, which means that any polynomial time algorithm for SAT would yield polynomial time algorithms for every problem in NP. Nevertheless recent randomized algorithms for finding satisfying assignments have been remarkably successful, both on industrial benchmarks and randomly generated sets of clauses. Careful choice of the distribution yields relatively hard instances, but there is a theorem that suggests that the hardest distributions are not the natural ones. Proving instances unsatisfiable is generally more difficult than finding satisfying assignments (when they exist). There has been recent progress in proving lower bounds on the complexity of unsatisfiability proofs.

About the Speaker:

Stephen A. Cook, University Professor at the University of Toronto, has advanced the study of theoretical computer science in profound and significant ways. The study of NP and NP-complete sets began, in many respects, with Cook's seminal 1971 paper in which it was shown that the Boolean formula satisfiability problem (SAT) is NP-complete. For that and for his many other achievements, he was awarded the Turing Award in 1982. He is also a fellow of the Royal Soc. of Canada,, the National Academy of Sciences of the United States, and the American Academy of Arts and Sciences. 


Remaining speakers in the Distinguished Lecturer Series of the
DIMACS Special Year on Logic and Algorithms are:
        Ed Clarke (Carnegie Mellon University), 
        Vaughn Pratt (Stanford University), 
        Alexander Razborov (Steklov Mathematical Institute).

For additional information about the DIMACS special year, please see the 
following web site:

    http://dimacs.rutgers.edu/archive/SpecialYears/1995_1996/


For additional information about the DIMACS special year, please see the 
following web site:

    http://dimacs.rutgers.edu/archive/SpecialYears/1995_1996/

Prof. Cook's talk is scheduled in conjunction with the Rutgers
Department of Computer Science Special Colloquium Series.
For more information about DCS colloquia, please see the following
web site:

    http://athos.rutgers.edu/pub/colloquia/

or contact Sven Dickinson (Colloquium Committee Chair) at x5-0021, x5-6154
or at sven@kiva.rutgers.edu.
Index
dimacs-www@dimacs.rutgers.edu
 Document last modified on February 27, 1996