# A set that is not polynomial time enumerable

For a set $$I\subseteq \Bbb N$$, defined $$s_{I}(n)=\min\{i\in I\mid i>n\}$$. The set $$I$$ is called polynomial-time-enumerable if $$s_I(n)$$ is computable in $$\mathsf{poly}(n)$$ time.

Most of the sets I can imagine are polynomial time enumerable. I am really looking for an example of a set of integers that is NOT polynomial time enumerable.

• A set $S \subseteq \mathbb{N}$ is undecidable if there is no Turing machine that on any input $n \in S$ halts, answering Yes, and on any input $n \notin S$ halts, answering No. – Yuval Filmus Nov 19 '20 at 17:46