Certification with an NP Oracle
summary
Checking a claimed certificate is coNP-complete, and under P ≠ NP no algorithm finds a certificate of size φ(k) for any rapidly growing φ. With access to an NP oracle the problem admits a BPP^NP algorithm that outputs a poly(k)-size certificate when f has certificate complexity ≤ k, while the instance-wise problem is NP^NP-hard to approximate: it is hard to distinguish a yes case with a size-k certificate from a no case where every certificate has size ≥ k·n^{1−ε}.
AI-written summary · about
chapters (9)
- 0:00Intro
- 0:16Explaining the behavior of black boxes
- 1:46Certificates as explanations
- 3:14Certificates in theory and in practice
- 6:54Given intractability, what to do?
- 7:36Why is certification "easy" for monotone f?
- 12:08The algorithmic problem we consider (revised)
- 12:32Result 1: Certification in BPPNP
- 14:02Result 2: Instance-wise certification is NPNP-hard
related talks
29mSubexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds
01h 02mFine-Grained Counting Complexity II
01h 02mFine-Grained Counting Complexity I
01h 04mLossy Kernelization
01h 32mInapproximability of Constraint Satisfaction Problems I
27mOn the Subexponential Time Complexity of the CSP
33mLower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems
30mParameterized Inapproximability of Max k-Subset Intersection under ETH