Eintrag in der Universitätsbibliographie der TU Chemnitz
Volltext zugänglich unter
URN: urn:nbn:de:bsz:ch1-qucosa-192509
Falke, Lutz
Goerdt, Andreas (Prof. Dr.) ; Veselić, Ivan (Prof. Dr.) (Gutachter)
Schwellwert für die Lösbarkeit von zufälligen Gleichungssystemen über Z3
Satisfiability Threshold of Random Equations over Z3
Kurzfassung in deutsch
Behandelt werden zufällige lineare Gleichungssysteme modulo 3, wobei in jeder Gleichung genau k Variablen vorkommen. Es wird gezeigt, dass der Schwellwert der Lösbarkeit solcher Gleichungssysteme bei der 2-Kern-Dichte von 1 liegt. Das Resultat ist eine Verallgemeinerung bereits bekannter Resultate für den modulo 2 Fall. Dabei entsteht der 2-Kern dadurch, dass wir alle Variablen mit nur einem Vorkommen löschen. Die Dichte ist definiert als der Quotient der Anzahl der Gleichungen durch die Anzahl der Variablen.Im Rückblick ist dieses Resultat ein natürlicher Schwellwert und die Vermutung liegt nahe, dass er bei analogen Situationen über anderen Strukturen als Z3 auch gelten sollte. Allerdings sind schon im modulo 2 Fall die analytischen Probleme nicht gering, und der hier behandelte Fall braucht weitere analytische Einsichten.
| Universität: | Technische Universität Chemnitz | |
| Institut: | Professur Theoretische Informatik | |
| Fakultät: | Fakultät für Informatik | |
| Dokumentart: | Dissertation | |
| Betreuer: | Goerdt, Andreas (Prof. Dr.) | |
| URL/URN: | http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-192509 | |
| SWD-Schlagwörter: | Theoretische Informatik | |
| Freie Schlagwörter (Deutsch): | Schwellwert , Zufällige Gleichungssysteme , Erfüllbarkeit | |
| Freie Schlagwörter (Englisch): | thresholds , random equations , satisfiability | |
| DDC-Sachgruppe: | Informatik, Informationswissenschaft, allgemeine Werke | |
| Tag der mündlichen Prüfung | 16.12.2015 |
