Matthias Hagen: Komplexität des Isomorphietestes monotoner Boolescher Formeln

Zwei Boolesche Formeln f und g sind isomorph gdw. es eine Permutation p der Variablen gibt, so dass f und p(g) äquivalent sind. Wir wollen das Isomorphieproblem für allgemeine Boolesche Formeln mit dem monotonen Fall vergleichen und beweisen, dass die beiden Probleme polynomialzeitäquivalent sind. Dies zeigt, dass eine Vermutung von Steffen Reith aus dem Jahre 2003 nicht zutrifft.