An algebraic analysis of Cook's Theorem showing that circuit satisfiability is NP-complete

Sala 0.04 (DMP)

Wednesday, 17 May, 2006 - 15:30

Using bi-machines and matrices with coefficients in certain semi-rings, we prove an algebraic version of Cook's Theorem.

Speaker:

John Rhodes (University of California, Berkeley)