Return to search

Schwellwert für die Lösbarkeit von zufälligen Gleichungssystemen über Z3

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.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:20371
Date16 December 2015
CreatorsFalke, Lutz
ContributorsGoerdt, Andreas, Veselić, Ivan, Technische Universität Chemnitz
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageGerman
Detected LanguageGerman
Typedoc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0018 seconds