  Boolean automata networks (aka Boolean networks) are space-time discrete
dynamical systems, studied as a model of computation and as a representative
model of natural phenomena. A collection of simple entities (the automata)
update their 0-1 states according to local rules. The dynamics of the network
is highly sensitive to update modes, i.e., to the schedule according to which
the automata apply their local rule. A new family of update modes appeared
recently, called block-parallel, which is dual to the well studied
block-sequential. Although basic, it embeds the rich feature of update
repetitions among a temporal updating period, allowing for atypical asymptotic
behaviors. In this paper, we prove that it is able to breed complex
computations, squashing almost all decision problems on the dynamics to the
traditionally highest (for reachability questions) class PSPACE. Despite
obtaining these complexity bounds for a broad set of local and global
properties, we also highlight a surprising gap: bijectivity is still coNP.
