0
$\begingroup$

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.

Thanks in advance.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Take any uncomputable set. $\endgroup$ – Yuval Filmus Nov 19 '20 at 15:31
  • $\begingroup$ when is a set of integers uncomputable? $\endgroup$ – QED Nov 19 '20 at 15:59
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 19 '20 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.