Theoretical Status Of Threshold

• Very challenging problem ...

• Current status:

  3SAT threshold lies between 3.003 and 4.8
  
  (Motwani et al. 1994; Broder and Suen 1993;
  Broder et al. 1992; Dubois 1990)

Previous slide

Next slide

Back to first slide

View graphic version