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.

$\endgroup$
3
  • 1
    $\begingroup$ Take any uncomputable set. $\endgroup$ Commented Nov 19, 2020 at 15:31
  • $\begingroup$ when is a set of integers uncomputable? $\endgroup$
    – QED
    Commented Nov 19, 2020 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$ Commented Nov 19, 2020 at 17:46

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.