Tushant Mittal University of Chicago

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