Aussagenlogische Beweiskomplexität und disjunkte NP-Paare I


Im Projekt werden starke aussagenlogische Beweissysteme wie Erweiterungen von Frege-Systemen und ihre Beziehungen zu disjunkten NP-Paaren untersucht. Ein zentrales Problem ist der Nachweis unterer Schranken für die Beweislänge für starke Beweissysteme (unter geeigneten komplexitätstheoretischen Voraussetzungen). Ein wichtiges Hilfsmittel bilden hierbei die mit dem Beweissystem assoziierten kanonischen NP-Paare.


Projektleitung
Köbler, Johannes Prof. Dr. (Details) (Algorithmen und Komplexität II)

Laufzeit
Projektstart: 04/2006
Projektende: 03/2008

Zuletzt aktualisiert 2020-09-03 um 23:13