← All problems

Superpolynomial circuit lower bounds for NP

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

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

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li