1 |
HAMMING DISTANCE PLOT TECHNIQUES FOR SLS SAT SOLVERS: EXPLORING THE BEHAVIOR OF STATE-OF-THE-ART SLS SOLVERS ON RANDOM K-SAT PROBLEMSZamora, Carlos Enrique, Jr 23 May 2019 (has links)
No description available.
|
2 |
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 hypergraphsSchädlich, Frank 05 July 2004 (has links) (PDF)
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. / 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.
|
3 |
Effizientes Verifizieren co-NP-vollständiger Probleme am Beispiel zufälliger 4-SAT-Formeln und uniformer HypergraphenSchädlich, Frank 30 June 2004 (has links)
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. / 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.
|
Page generated in 0.0295 seconds