  We consider two algorithmic problems concerning sub-semigroups of Heisenberg
groups and, more generally, two-step nilpotent groups. The first problem is
Intersection Emptiness, which asks whether a finite number of given finitely
generated semigroups have empty intersection. This problem was first studied by
Markov in the 1940s. We show that Intersection Emptiness is PTIME decidable in
the Heisenberg groups $\operatorname{H}_{n}(\mathbb{K})$ over any algebraic
number field $\mathbb{K}$, as well as in direct products of Heisenberg groups.
We also extend our decidability result to arbitrary finitely generated 2-step
nilpotent groups.
  The second problem is Orbit Intersection, which asks whether the orbits of
two matrices under multiplication by two semigroups intersect with each other.
This problem was first studied by Babai et al. (1996), who showed its
decidability within commutative matrix groups. We show that Orbit Intersection
is decidable within the Heisenberg group $\operatorname{H}_{3}(\mathbb{Q})$.
