  The subitemset isomorphism problem is really important and there are
excellent practical solutions described in the literature. However, the
computational complexity analysis and classification of the BZ (Bundala and
Zavodny) subitemset isomorphism problem is currently an open problem. In this
paper we prove that checking whether two sorting networks are BZ isomorphic to
each other is GI-Complete; the general GI (Graph Isomorphism) problem is known
to be in NP and LWPP, but widely believed to be neither P nor NP-Complete;
recent research suggests that the problem is in QP. Moreover, we state the BZ
sorting network isomorphism problem as a general isomorphism problem on
itemsets --- because every sorting network is represented by Bundala and
Zavodny as an itemset. The complexity classification presented in this paper
applies sorting networks, as well as the general itemset isomorphism problem.
The main consequence of our work is that currently no polynomial-time algorithm
exists for solving the BZ sorting network subitemset isomorphism problem;
however the CM (Choi and Moon) sorting network isomorphism problem can be
efficiently solved in polynomial time.
