Consider the following decision problem:

Given a two integers $n$ and $k$, decide whether $k=\lfloor n\pi\rfloor$

Question: Is this problem known to be in $P$?

Although this may look like a stupid question, I believe it is not. The reason is that the classical model of computation is inherently discrete, and it is not clear what is the complexity of computing functions such as $n\mapsto \lfloor n\pi\rfloor$. What I can prove so far is the following:

Claim: There exists an algorithm that computes in time $n^{O(1)}$ an rational number $k$ such that $|k-n\pi|<1$.

Proof. The algorithm is based on the Leibniz formula: $\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\dots$ It is not difficult to show that we can compute the sum of the first $n$ terms in time $poly(n)$ to get an approximation $\hat{\pi}$ of $\pi$ such that $|\pi-\hat{\pi}|=O(1/n)$. Then, the algorithm outputs $k:=n\hat{\pi}$.

However, this does not really answer the question above. It might be for example that for any constant $\gamma$, there exists an integer $n_\gamma$ for which $n_\gamma\pi-\lfloor n_\gamma\pi\rfloor<\frac{1}{n^\gamma}$. If this is true, then whatever polynomial number of terms the algorithm of the claim would calculate, it would fail to compute $\lfloor n\pi\rfloor$ for at least one input integer $n$.

I'm interested in any interesting thoughts or references related to this type of questions.

  • 6
    $\begingroup$ $n^{O(1)}$ is not polynomial time, but exponential, as the input has length $\log n$. But you can compute $\lfloor n\pi\rfloor$ in time $O(M(\log n)\log\log n)=\log n\,(\log\log n)^{O(1)}$ (where $M(m)$ is the compexity of $m$-bit integer multiplication). See e.g. mathoverflow.net/questions/433675/… . $\endgroup$ Nov 17, 2022 at 15:26
  • 6
    $\begingroup$ In particular, the scenario in your penultimate paragraph cannot happen, because $\pi$ has finite irrationality measure. $\endgroup$ Nov 17, 2022 at 15:29


Your Answer

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