Martin Mundhenk: On proving circuit lower bounds against the polynomial-time hierarchy

1982 zeigte Kannan, dass es für jedes k eine Sprache L_k in NP^(NP) (das ist die Klasse "\Sigma_2^p") gibt, für die es keine Schaltkreise der Größe n^k gibt. Der Beweis von Kannan war nicht-konstruktiv. Kürzlich haben Cai und Watanabe einen konstruktiven Beweis mit einem schönen Trick gefunden.