ColloquiaTalk by Lance Fortnow on Wed. February 19

[Margery Ishmael]

----------------------------------------------------------------------------

DEPARTMENT OF COMPUTER SCIENCE - TALK

Wed. February 19, 2003 at 2:30 pm in Ryerson 251

----------------------------------------------------------------------------

Speaker: LANCE FORTNOW
From: NEC Laboratories America


Title: "The Computational Complexity of Satisfiability"

Abstract:
Ever since Steve Cook showed it NP-complete in 1971, the Boolean Formula 
Satisfiability problem has consumed the minds of computer scientists. 
Whether Satisfiability is in P, the famous P versus NP problem, has 
remained the biggest question in theoretical computer science and one of 
the most important in all of mathematics. Attempts to understand the 
Satisfiability problem have spawned whole areas of research in 
computational complexity.

We survey a number of computational complexity questions related to 
Satisfiability, including:
· Can we show any time or space lower bounds for solving Satisfiability?
· A satisfying assignment gives a proof that a formula is satisfiable. Can 
one prove that a formula is not satisfiable?
· Are two Satisfiability instances more powerful than one?
· Is Satisfiability the same as every other NP-complete problem?
· Does Satisfiability have fast random, biological or quantum algorithms?
We will also touch on the prospects of solving the P versus NP question in 
the near future.

*Refreshments to follow in Ryerson 255*

Host: Stuart Kurtz