Detailseite
Projekt Druckansicht

Stochastische Lokale Suche bei SAT-Solvern

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2011 bis 2014
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 206226417
 
In diesem Projekt wird die Algorithm Engineering Methode auf SAT-Solving angewandt, und zwar speziell auf solche SAT-Algorithmen, die auf dem Konzept der lokalen Suche beruhen. Die Ziele des Projekts gliedern sich in 3 Punkte: Zum ersten sollen effizientere SAT-Solver entwickelt und implementiert werden. Diese werden der internationalen Szene auf der SAT-Konferenz präsentiert bzw. bei dem SAT-Kontest 2013 eingereicht. Zweitens, die Lücke zwischen den bei Algorithmen-Experimenten beobachteten Laufzeiten und den theoretischen Analysen derartiger Algorithmen soll weiter geschlossen werden; und dies ebenso auf der praktischen wie auf der theoretischen Seite. Zum dritten, wegen des generischen Charakters des SAT-Problems als ein NP-vollständiges Problem, und ebenso, wegen des generischen Charakters der Lokale Such-Methode, sollen die erzielten Resultate es ermöglichen, auch auf andere Problemstellungen angewandt zu werden.
DFG-Verfahren Schwerpunktprogramme
 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung