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$.

  • $\begingroup$ In the second paragraph you get an algorithm polynomial in $n$ not necessarily polynomial in $\log n$. Is this correct? $\endgroup$
    – user409739
    Oct 15 at 8:13
  • $\begingroup$ When I say polynomial, I always mean polynoimal in the length of the input (or output), i.e., in your notation, $\log n$. $\endgroup$ Oct 15 at 8:47
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 15 at 8:53
  • $\begingroup$ Can you clarify how you compute $y$ in polynomial time in $\log m$? $\endgroup$
    – user409739
    Oct 15 at 8:59
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 15 at 9:44

Your Answer

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