Eintrag in der Universitätsbibliographie der TU Chemnitz
Volltext zugänglich unter
URN: urn:nbn:de:swb:ch1-200400959
Schädlich, Frank
Goerdt, Andreas (Prof. Dr.) ; Lefmann, Hanno (Prof. Dr.) ; Steger, Angelika (Prof. Dr.) (Gutachter)
Effizientes Verifizieren co-NP-vollständiger Probleme am Beispiel zufälliger 4-SAT-Formeln und uniformer Hypergraphen
Efficient verification of co-NP-complete like random 4-SAT and uniform hypergraphs
Kurzfassung in deutsch
Das NP-vollständige Problem k-SAT ist von zentraler Bedeutung in der theoretischen Informatik. In der Dissertation werden zufällige 4-SAT-Formeln mit > n^2 vielen Klauseln studiert. Diese Formeln sind mit hoher Wahrscheinlichkeit unerfüllbar.Hier wird erstmalig die Existenz eines Algorithmus gezeigt, der diese Unerfüllbarkeit effizient verifiziert. Hierfür wird die geringe Diskrepanz von Hypergrpahen und Multigraphen betrachtet. Der Schlüssel zu diesem Algorithmus liegt in der Kombination von spektralen Techniken mit Approximationsalgorithmen der klassischen kombinatorischen Optimierung.
Der vorgestellte Algorithmus kann auf den effizienten Nachweis der Unerfüllbarkeit von Not-All-Equal-4-SAT-Formeln und die Nicht-2-Färbbarkeit von 4-uniformen Hypergraphen erweitert werden.
Es wird ebenfalls eine Erweiterung der Hajos-Konstruktion nicht k-färbbarer Graphen auf nicht k-färbbare uniforme Hypergraphen angegeben.
Kurzfassung in englisch
The NP-complete k-SAT problem - decide wether a given formula is satisfiable - is of fundamental importance in theoretical computer science. In this dissertation we study random 4-SAT formulas with > 116 n^2 clauses. These formulas are almost surly unsatisfiable.Here we show the existence of a polynomial time algorithm that certifies the unsatisfiability. Therefore we study the discrepancy of hypergraphs and multigraphs. We also combine spectral techniques with approximation algorithms to achieve the new result.
Our new algorithm is adaptable for Not-All-Equal-4-SAT and the 2-colouring of 4-uniform hypergraphs.
We also extends the Hajos construction of non k-colourable graphs to non k-colourable uniform hypergraphs.
| Universität: | TU Chemnitz | |
| Institut: | Professur Theoretische Informatik | |
| Fakultät: | Fakultät für Informatik | |
| Dokumentart: | Dissertation | |
| Betreuer: | Goerdt, Andreas (Prof. Dr.) | |
| URL/URN: | http://archiv.tu-chemnitz.de/pub/2004/0095 | |
| Freie Schlagwörter (Deutsch): | Approximationstechniken , Erfüllbarkeit , probabilistische Analyse , probabilistisches 4-SAT , probabilistisches k-SAT , Hajos-Kalkül , Hypergraphdiskrepanz , maximaler Schnitt | |
| Freie Schlagwörter (Englisch): | probabilistic analysis , random k-SAT , random 4-SAT , Hajos calculus , Maxcut , Satisfiability , approximation techniques , hypergraph discrepancy | |
| DDC-Sachgruppe: | Mathematik, Datenverarbeitung; Informatik | |
| Tag der mündlichen Prüfung | 30.06.2004 |
