Seol mar théacs é seo: Complexity of restricted variants of Skolem and related problems