NoPe- Not so easily

Tushant Mittal University of Chicago

Abstract

What’s the big deal about proving something is in NP? Just guess and check. Or so thinks the insouciant young complexity theorist. Surely, there are problems that do not admit efficient NP certificates but it is tricky to come up with natural problems which we believe must be in NP but the proof is non-trivial. We discuss a quick proof that one very natural problem is in NP (which actually is in P). We then look at a larger family of examples and depending on the time, mention new results/open problems.

Date
Apr 6, 2022 12:30 PM — 1:30 PM
Event
Theory Lunch
Location
JCL 390

Join via Zoom