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

Using bi-machines and matrices with coefficients in certain semi-rings, we prove an algebraic versio

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

Date and Venue

Start Date

May 17, 2006 | 16:30

Venue

Sala 0.04 (DMP)

John Rhodes (University of California, Berkeley)

Semigroups, Automata and Languages