self reducible in p-time

Question

We say that a language 𝐿 is 𝑘-self-reducible if there exists a function 𝑓 such that:

1. 𝑓 is computable in polynomial time, and
2. There exists $𝑛_0 ∈ ℕ$ such that for all 𝑥 of length at least $𝑛_0$, the function 𝑓 returns a list of 𝑘 strings $𝑦_1, 𝑦_2, … , 𝑦_𝑘$ that are all shorter than 𝑥 (i.e., $|𝑦_𝑖| < |𝑥|$ for all $1 ≤ 𝑖 ≤ 𝑘$), and in addition $𝑥 ∈ 𝐿 ⟺$ There exists $𝑖$ such that $𝑦_𝑖 ∈ 𝐿.$

Is $𝐿 ∈ P$, if a language 𝐿 is 1-self-reducible?

Answer 1

Yes. Here is how to build a polynomial-time algorithm. It has hardcoded the list of all $x \in L$ whose length is $\le n_0$. For any longer $x$, keep applying $f(\cdot)$ until the result has length $\le n_0$. This correctly computes $f$.

What is its running time? When this is run on an input $x$, it applies $f$ at most $n$ times, where $n$ is the length of $x$. A polynomial times $n$ is another polynomial, so its running time is polynomial.