2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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$
    – Emil Jeřábek
    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$
    – Emil Jeřábek
    Nov 17, 2022 at 15:29

0

Reset to default

Your Answer

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