Der Wettlauf um das Kochen-Specker-Theorem

TU Wien mit Weltrekord

Ein Weltrekord beim Lösen von Erfüllbarkeitsproblemen gelang am am 27.07.2023 am Institute of Logic and Computation der TU Wien – er ist recht abstrakt, aber die Technologie dahinter ist äußerst wichtig für Hard- und Softwareindustrie. Angenommen, Alice, Bob und Carla beantworten eine Frage. Jede der drei Antworten ist entweder richtig oder falsch. Ist es logisch möglich, dass mindestens zwei der Antworten richtig sind, mindestens eine falsch ist und außerdem gilt: Weder trifft es zu, dass Bob und Carla beide richtig liegen, noch dass Alice und Bob beide richtig liegen? Das klingt vielleicht etwas verworren, ist aber ein typisches Beispiel für ein Erfüllbarkeitsproblem (auch SAT-Problem, vom englischen „satisfiability“). weiterlesen…