Schaltkreiskomplexität #15 - Untere Schranken
Aus der Schaltkreiskomplexität ergibt sich ein Ansatz um P ungleich NP zu zeigen, nämlich indem man zeigt, dass es für SAT keine Schaltkreisfamilie polynomieller Größe gibt. In diesem Video sehen wir uns einige Resultate an, die hiermit in Verbindung stehen.