  We study the computational complexity of model checking and satisfiability
problems of polyadic modal logics extended with permutations and Boolean
operators on accessibility relations. First, we show that the combined
complexity of the model checking problem for the resulting logic is
PTime-complete. Secondly, we show that the satisfiability problem of polyadic
modal logic extended with negation on accessibility relations is
ExpTime-complete. Finally, we show that the satisfiability problem of polyadic
modal logic with permutations and Boolean operators on accessibility relations
is ExpTime-complete, under the necessary assumption that the number of
accessibility relations that can be used is bounded by a constant.
