Project Details
Projekt Print View

Beweiskomplexität im Kontext beschränkter Arithmetik

Applicant Dr. Klaus Aehlig
Subject Area Theoretical Computer Science
Term from 2006 to 2007
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 29735564
 
Beweiskomplexität studiert die Längen aussagenlogischer Beweise mit dem Fernziel, den Unterschied zwischen den Komplexitätsklassen NP und co-NP zu verstehen. Untere Schranken an die Länge von Beweisen sind hierbei von besonderem Interesse. Systeme beschränkter Arithmetik charakterisieren wichtige Komplexitätsklassen über ihre beweisbar totalen Funktionen. Das Ziel des Studiums dieser Systeme ist, die zu Grunde liegenden Komplexitätsklassen besser zu verstehen und zu erkennen welche Definitionsprinzipien die Mächtigkeit einer Komplexitätsklasse ausmachen. Resultate über den Zusammenhang solcher Systeme für verschiedene Komplexitätsklassen sind für sich genommen interessant. Zwischen Systemen beschränkter Arithmetik und aussagenlogischen Beweissystemen besteht ein enger Zusammenhang mittels propositionaler Übersetzungen. Dies ermöglicht Rückschlüsse von Beweislängen auf Trennungsresultate beschränkter Arithmetik, und umgekehrt. Im beantragen Forschungsvorhaben sollen zweitstufige Systeme beschränkter Arithmetik untersucht werden vermöge Abschätzungen über Länge und Gestalt der dazugehörigen Beweis Systeme. Ziele sind Trennungsresultate und die Entwicklung einer geeigneten Skala zur Messung der Stärke der betrachteten Systeme.
DFG Programme Research Fellowships
International Connection Canada
 
 

Additional Information

Textvergrößerung und Kontrastanpassung