QBF Deutschland kündigt SAT Solver mit Polynomiallaufzeit an

(openPR) Die Entwicklung von Algorithmen, die das Entscheidungsproblem der Aussagenlogik (SAT) in angemessener Zeit lösen können ist seit der Entdeckung von SAT Gegenstand größter Bemühungen.

Das Wiesbadener Unternehmen QBF Deutschland, welches im Bereich der Digitalisierung und Automatisierung Dienstleistungen für Unternehmen erbringt, beschäftigt sich in einem seiner Projekte mit der Entwicklung von Algorithmen, die als schwierig geltende Probleme zügig lösen können. SAT gilt dabei als “Urvater” der sogenannten NP-Probleme, da sich jedes dieser Probleme in ein solches Entscheidungsproblem umformulieren lässt. NP-Probleme sind, grob formuliert solche, die sich im Allgemeinen schwierig lösen lassen, jedoch ist es oftmals einfach eine gegebene Lösung auf ihre Richtigkeit zu überprüfen.

Es galt lange Zeit als umstritten, in großen Teilen der Community sogar als unmöglich, dass die sogenannten NP-Probleme in Polynomialzeit lösbar wären. Sollte sich nun herausstellen, dass der Algorithmus tatsächlich immer funktioniert, wird damit auch eine grundlegende Frage der theoretischen Informatik beantwortet werden, nämlich ob die NP-Probleme zu denjenigen gehören, die man als “praktisch lösbar” betrachtet.

Neben dem Algorithmus QBF 3-SAT Type 1, der bestimmte Probleme effizient lösen kann, hat das Team von QBF mit seinem Prototypen QBF 3-SAT Type 0 einen Algorithmus entwickelt, der bislang alle Probleme dieser Art in Polynomialzeit lösen konnte. Derzeit beschäftigt sich das “Team Mathematik und theoretische Informatik” mit der Konstruktion eines SAT Problems, das von dem Algorithmus nicht schnell gelöst werden kann. Sollte die Konstruktion dieses Problems allerdings scheitern, wird ein für alle mal geklärt sein, dass QBF's Algorithmus alle NP-Probleme praktisch lösen kann.

Der Inhaber von QBF Deutschland, Christopher Heiling kündigt unterdessen an, dass es keine Veröffentlichung des SAT Solvers geben wird, bevor ein mathematisch rigoroser Beweis für seine Funktionalität vorliegt und eine Abschätzung der Folgen für die Internetsicherheit erfolgt ist.