On the effective generation of set elements within specified ranges

From MaRDI portal





This paper looks at the problem of determining whether a set \(A\) contains an element in some effectively given finite interval. The interval is specified by a recursive function \(g\geq\text{id}\) as \([n,g(n)]\). It is noted that this problem has an effective solution for some \(g\) iff \(A\) is not hyperimmune. Some related questions are answered. All results are very easy to prove. In the end it is suggested that this investigation might provide some hints for the polynomial-time version of the problem. In the reviewer's opinion this is rather unlikely.











This page was built for publication: On the effective generation of set elements within specified ranges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3141999)