Wissenschaftsdisziplinen
Informatik (40%); Mathematik (60%)
Keywords
Proof complexity,
Homomorphism,
Satisfiability Problem,
Symmetry rule,
Resolution,
Fixed Parameter Complexity
Abstract
In unserer bisherigen Arbeit konnten wir zeigen, dass im Resolutionssystem die Homomorphismusregel tatsächlich
eine exponentielle Beweisverkürzung gegenüber Krishnamurthys Symmetrieregel erlaubt. Es ist geplant, die
Studien auf das für praktische Anwendungen wichtige Problem der Beweissuche auszudehnen und den
algorithmischen Aspekt der Homomorphismusregel zu untersuchen.
Einen weiteren Schwerpunkt bildet die Parametrisierte Komplexitätstheorie: Im Zusammenhang unserer kürzlich
erzielten Ergebnisse zum parametrisierten Erfüllbarkeitsproblem (SAT), ergibt
sich die Frage nach der parametrisierten Komplexität der SAT-Hierachie von Gallo und Scutell und deren
Verallgemeinerungen.
Weiters werden wir die Anwendbarkeit verschiedener Konzepte aus dem Gebiet der Graphenhomomorphismen auf
Klauselmengen untersuchen, insbesondere Nesetrils Verallgemeinerung der Hajs-Konstruktion.