In dieser Arbeit wird das folgende Entscheidungsproblem hinsichtlich seiner Komplexität untersucht. Gegeben ist ein Plan eines Open-Shop Schedulingproblems über einer beliebigen Operationenmenge. Ist dieser Plan irreduzibel? In einer Formulierung mittels sogenannter H-Comparabilitygraphen lautet die Problemstellung für das komplementäre Problem co-IRREDUCIBILITY: "Existiert ein Comparabilitygraph G*, der ein echter Teilgraph von G ist und G(SIJ) als Teilgraph enthält?", wobei G(SIJ) der zu der Operationenmenge SIJ gehörende induzierte Teilgraph des Hamming-Graphen Kn × Km, und G der H-Comparabilitygraph zu dem gegebenen Ausgangsplan ist. Trotz der Ähnlichkeit ist dieses Problem kein Spezialfall des COMPARABILITY-GRAPH-SANDWICH Problems, dessen NP-Vollständigkeit bekannt ist. Bekannt ist die Zugehörigkeit von IRREDUCIBILITY zu co-NP. Untersucht werden die Bedingungen, unter denen IRREDUCIBILITY in NP, und damit im Schnitt von NP und co-NP (= ZPP*), oder sogar in P liegt. Es wird ein Algorithmus vorgestellt, der reduzierbare Pläne nichtdeterministisch reduziert, und irreduzible Pläne nur unter sehr engen Voraussetzungen nicht als irreduzibel erkennen kann. Basierend auf begründeten Zweifeln an der Existenz von Instanzen, die diese engen Voraussetzungen erfüllen, wird vermutet, dass IRREDUCIBILITY in NP liegt. Bei Richtigkeit dieser Vermutung liegt IRREDUCIBILITY entweder in P, oder in NP-incomplete = NP − (P + NP-complete). Die Hinweise auf die Zugehörigkeit zu P werden diskutiert.
