Minimum Circuit Size Problem
The Minimum Circuit Size Problem, its multi-output and gap variants, and their role in meta-complexity.
| Status | Statement | Tags |
|---|---|---|
|
iO Overhead, Single-Output The first of the source’s named main open problems. Its main theorem gives an Omega(s/log s) additive overhead lower bound for iO on multi-output circuits under NP not in BPP – an assumption that is minimal, since a zero-overhead scheme exists if NP is in BPP. The single-output case is not covered, and the source says why: its route runs through NP-hardness of Multi-MCSP. 4 open |
Black Box SeparationsMinimum Circuit Size ProblemOne Way Functionslower-boundbarrier (ai) |
No matching items