6.3 Komplexitätsüberlegungen

Bevor die in Venn-Diagrammen üblichen Operationen auf Algorithmen abgebildet werden, sind einige grundsätzliche Komplexitätsüberlegungen sinnvoll.

Die den Algorithmen zugrundeliegende Datenstruktur ist ein Array oder eine lineare Liste mit der Größe $2^{n}$, wenn $n$ die Anzahl der betrachteten Objekte ist. Obwohl die Algorithmen mit einer Laufzeit von $O(N)$ über der Eingabemenge $N$ auskommen, so haben sie doch letztlich exponentielle Laufzeit, denn die Eingabemenge steigt exponentiell an bezogen auf $n$. Die Laufzeit ist korrekt angegeben mit $O(2^{n})$. Das ist kein gutes Ergebnis, aber letztlich war nichts anderes zu erwarten, denn logische Probleme sind bekannt für exponentielle Laufzeiten.

Für den zweiwertigen Fall gilt: Das Erfüllbarkeitsproblem der Aussagenlogik ist NP-vollständig. Das Folgerungsproblem der Aussagenlogik ist coNP-vollständig, da auf Unerfüllbarkeit geprüft werden muß. Für die Aussagenlogik gibt es Algorithmen, die das Folgerungsproblem mit einer etwas geringeren Laufzeit als $O(2^{n})$ lösen.

Die zweiwertigen Booleschen Verbände sind ein Spezialfall der allgemeinen Booleschen Verbände, besonders auch in bezug auf das Folgerungsproblem. Die Venn-Diagramme repräsentieren allgemeine Boolesche Verbände, sind mit zweiwertigen sozusagen etwas unterfordert. Daher kann man für diesen Fall nicht erwarten, daß die Diagramme mit speziell auf die Aussagenlogik zugeschnittenen Algorithmen konkurrieren können.