- If SAT does not have polynomial-size circuits then SAT then Σ2p∩Π2p which contains SAT does not have nk-size circuits.
- If SAT has polynomial-size circuits then Σ4p=Σ2p∩Π2p (Karp-Lipton) and thus Σ2p∩Π2p does not have nk-size circuits.
Vinod Variyam recently observed that the class PP which is not known to contain S2p also cannot have nk-size circuits. Here is his proof: If PP has nk-size circuits then PP is in P/poly which implies the polynomial-time hierarchy and in particular Σ2p is in MA which is in PP which has nk-size circuits contradicting Kannan.
Read Variyam's paper for details and references.