  In 1978, Schaefer proved his famous dichotomy theorem for generalized
satisfiability problems. He defined an infinite number of propositional
satisfiability problems (nowadays usually called Boolean constraint
satisfaction problems) and showed that all these satisfiability problems are
either in P or NP-complete. In recent years, similar results have been obtained
for quite a few other problems for Boolean constraints.Almost all of these
problems are variations of the satisfiability problem.
  In this paper, we address a problem that is not a variation of
satisfiability, namely, the isomorphism problem for Boolean constraints.
Previous work by B\"ohler et al. showed that the isomorphism problem is either
coNP-hard or reducible to the graph isomorphism problem (a problem that is in
NP, but not known to be NP-hard), thus distinguishing a hard case and an easier
case. However, they did not classify which cases are truly easy, i.e., in P.
This paper accomplishes exactly that. It shows that Boolean constraint
isomorphism is coNP-hard (and GI-hard), or equivalent to graph isomorphism, or
in P, and it gives simple criteria to determine which case holds.
