On the complexity of feasibility, connectivity, and $2^a$-isogeny computation