<p>Consider the following decision problem:</p>
<blockquote>
<p>Given a two integers <span class="math-container">$n$</span> and <span class="math-container">$k$</span>, decide whether <span class="math-container">$k=\lfloor n\pi\rfloor$</span></p>
</blockquote>
<p><strong>Question:</strong> Is this problem known to be in <span class="math-container">$P$</span>?</p>
<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 <span class="math-container">$n\mapsto \lfloor n\pi\rfloor$</span>. What I can prove so far is the following:</p>
<p><strong>Claim:</strong> There exists an algorithm that computes in time <span class="math-container">$n^{O(1)}$</span> an <em>rational</em> number <span class="math-container">$k$</span> such that <span class="math-container">$|k-n\pi|&lt;1$</span>.</p>
<p><em>Proof.</em> The algorithm is based on <a href="https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80" rel="nofollow noreferrer">the Leibniz formula</a>: <span class="math-container">$\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\dots$</span> It is not difficult to show that we can compute the sum of the first <span class="math-container">$n$</span> terms in time <span class="math-container">$poly(n)$</span> to get an approximation <span class="math-container">$\hat{\pi}$</span> of <span class="math-container">$\pi$</span> such that <span class="math-container">$|\pi-\hat{\pi}|=O(1/n)$</span>. Then, the algorithm outputs <span class="math-container">$k:=n\hat{\pi}$</span>.</p>
<p>However, this does not really answer the question above. It might be for example that for any constant <span class="math-container">$\gamma$</span>, there exists an integer <span class="math-container">$n_\gamma$</span> for which <span class="math-container">$n_\gamma\pi-\lfloor n_\gamma\pi\rfloor&lt;\frac{1}{n^\gamma}$</span>. If this is true, then whatever polynomial number of terms the algorithm of the claim would calculate, it would fail to compute <span class="math-container">$\lfloor n\pi\rfloor$</span> for at least one input integer <span class="math-container">$n$</span>.</p>
<p>I'm interested in any interesting thoughts or references related to this type of questions.</p>

CC BY-SA 4.0
2022-11-17T15:26:35.520Z
$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. https://mathoverflow.net/questions/433675/can-we-compute-the-first-n-digits-of-pi-in-fn-time .
Emil Jeřábek
CC BY-SA 4.0
2022-11-17T15:29:01.717Z
In particular, the scenario in your penultimate paragraph cannot happen, because $\pi$ has finite irrationality measure.
Emil Jeřábek
<cc.complexity-theory><np-hardness><turing-machines><polynomial-time>
Computing real numbers with Turing Machines
Mathieu Mari
# Computing real numbers with Turing Machines

(Asked by: username_0 on 2022-11-17)

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](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80): $\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.

**Tags:** cc.complexity-theory, np-hardness, turing-machines, polynomial-time

> **Comments:**
> **username_1**: $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. https://mathoverflow.net/questions/433675/can-we-compute-the-first-n-digits-of-pi-in-fn-time .  
> **username_1**: In particular, the scenario in your penultimate paragraph cannot happen, because $\pi$ has finite irrationality measure.  

---

## 0 answers

