Using bi-machines and matrices with coefficients in certain semi-rings, we prove an algebraic versio
Title
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 version of Cook's Theorem.
Date and Venue
Start Date
Venue
Sala 0.04 (DMP)
Speaker
John Rhodes (University of California, Berkeley)
Area
Semigroups, Automata and Languages