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
• Host: Professor Stephen A. Cook