# Family of PTIME sets where it is hard to name elements

Call a function$$\mathbb{N}\times \mathbb{N}\to \{0, 1\}, \quad (n, m)\to f(n, m)$$computable in polynomial time in $$\log n+\log m$$ a PTIME family.

Given a PTIME family $$f$$ call a computable function $$g:\mathbb{N}\to \mathbb{N}$$ such that $$f(n, g(n))=1$$ for all $$n\in \mathbb{N}$$ a solution of $$f$$.

Is there a PTIME family $$f$$ that has at least one solution and such that for each solution $$g$$ and each polynomial $$P$$ there exists $$n\in \mathbb{N}$$ such that the running time of $$g$$ on $$n$$ is more than $$P(\log n+\log g(n))$$?

The reason for taking $$\log n+\log g(n)$$ is to ensure that neither input nor output dominates the running time of the algorithm.

$$\log 0=0$$ by convention.

This is an open problem.

If $$\mathrm{TFNP\ne FP}$$, then a TFNP problem outside FP directly gives what you call a PTIME family (with solutions polynomially bounded in terms of the input) whose solutions cannot be computed in polynomial time.

If P = NP, then no such problem exists: the assumption implies that given $$n$$ and $$m$$, we can compute in polynomial (in $$\log n$$ and $$\log m$$) time a solution $$y$$ such that $$f(n,y)=1$$ and $$y\le m$$ if it exists (see e.g. Arora&Barak, Theorem 2.18). Let’s call this algorithm $$h(n,m)$$. Then successively call $$h(n,1)$$, $$h(n,2)$$, $$h(n,4)$$, $$h(n,8)$$, ... until you find a solution; this will take time polynomial in $$\log n$$ and $$\log y$$ where $$y$$ is the least solution, because the last call of $$h(n,m)$$ will be made with $$m\le 2y$$.

• In the second paragraph you get an algorithm polynomial in $n$ not necessarily polynomial in $\log n$. Is this correct?
– user409739
Oct 15 at 8:13
• When I say polynomial, I always mean polynoimal in the length of the input (or output), i.e., in your notation, $\log n$. Oct 15 at 8:47
• Oh, I see that it’s written wrong in the last sentence. I really wish you used standard notation, writing $n$ for the input itself rather than its length is EXTREMELY confusing. Oct 15 at 8:53
• Can you clarify how you compute $y$ in polynomial time in $\log m$?
– user409739
Oct 15 at 8:59
• Basically, anything else than $n$, $m$; also, $i$, $j$, $k$ are best avoided as they look like small integers. $x$, $y$ are one possibility; $a$, $b$ also work, or say, $r$, $s$. When dealing with strings, $w$ (for word) is quite common. Often capital letters such as $X$ are used (distinguishing them from small letters used for lengths, indices, etc.); some authors even use the convention that $N$ is a number/string of length $n$, $M$ of length $m$, etc. Oct 15 at 9:44