← All problems

Superpolynomial circuit lower bounds for NP

Does there exist a language L∈NPL\in NP such that every family of Boolean circuits deciding LL has superpolynomial size?

Equivalently, is NP⊈P/polyNP \not\subseteq P/poly?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu