Talks
Spring 2021

The Dawn of Computational Complexity Theory

Thursday, Mar. 11, 2021 8:30 am9:30 am

Add to Calendar

Speaker: 

Dick Karp (UC Berkeley)

Location: 

Zoom

The speaker will describe the early development of the fields of combinatorial optimization  and computational complexity theory, leading to the P vs. NP question, the centrality of the satisfiability problem, the identification of many combinatorial problems as NP-complete, and the challenge of coping with NP-complete problems in practice.