Zhegalkin Polynomialer SAT-Löser

Polynomiale Systeme sind grundlegende Werkzeuge für die Lösung schwieriger Probleme in Wissenschaft und Technik wie Robotik, automatisches Denken, künstliche Intelligenz und Signalverarbeitung. In ähnlicher Weise bilden boolesche Variablen seit den Anfängen des digitalen Zeitalters die Grundlage für Computeroperationen. Daher wird die Anwendung allgemeiner algebraischer Techniken auf die Boolesche Algebra heute als Methode zur Lösung komplexer Boolescher Gleichungssysteme verwendet, die früher nur mit Hilfe von Techniken der Booleschen Logik gelöst werden sollten. In diesem Projekt soll gezeigt werden, dass Zhegalkin-Polynome (auch bekannt als Algebraische Normalform - ANF) eine alternative Methode zur Darstellung boolescher Funktionen sind. Um die Hypothese zu testen, wurde ein Zhegalkin SAT Solver (ZPSAT) entwickelt. Die nach dem Test durchgeführten Ergebnisse ergaben, dass ZPSAT eine Konjunktion von XOR-Gleichungen in Bezug auf Zuverlässigkeit und Rechenzeit effizient lösen kann. Die Heuristik, die zur Erstellung von ZPSAT verwendet wurde, basiert hauptsächlich auf den Konzepten der Horn-Formeln und einer Schnell-Multiplikationsmethode von zwei ANF-Polynomen, die als Mobius-Transformation bekannt ist.