Attempt to find a real number whose computation of bits is NP-complete

Question

Recall that every real number $x$ can be expressed as $b + m$, where $b \in \mathbb{Z}$ is the integral part and where $m \in [0,1)$ is the mantissa.

Definition. A real number $x$ is said to be in a complexity class $\mathsf{C}$ if the decision problem asking whether the $n$-th bit below the radix point of the binary expansion of the mantissa of $x$ is 1ドル$ belongs to the complexity class $\mathsf{C}$.

By this definition, real numbers that are in $\mathsf{P}$ include:

• Every rational number
• $e$
• $\pi$
• $\ln 2$
• Champernowne's constant on base 2

And real numbers that are in $\mathsf{RE}$ but not in $\mathsf{R}$ include:

• The limit of the Specker sequence
• Chaitin's constant

My question is this: What is an example of a real number that is $\mathsf{NP}$-complete?

My attempt to come up with one was this. Consider the OEIS sequence A002562, the sequence of solutions of the $n$-queens problem up to symmetry. Since the $n$-queens problem is $\mathsf{\#P}$-complete, we can turn this sequence to an $\mathsf{NP}$-complete bit sequence by asking whether there is an odd number of solutions. The explicit resulting real number is 0ドル.100101000011101111001000010..._2$.

Is my solution right? Are there any examples that are more notable?

• orlp: A problem count(X) being #P-complete does not mean that count(X) % 2 == 1 is NP-complete.
• rus9384: Asking if the amount of solutions is odd is a problem in $\oplus\mathsf P,ドル which is not known to be either a subset or a superset of $\mathsf{NP}$. To make it belong to $\mathsf{NP},ドル you have to ask if there is at least 1ドル$ (or $k$ that is a number polynomial in $n$) solution.

Answer 1

Is $n$ given to the algorithm in unary or in binary?

• If $n$ is in binary, then I fail to see why numbers such as $e$, $\pi$, or $\ln2$ should be computable in polynomial time. I’m pretty sure it’s only known that they are computable in the counting hierarchy (something like $\mathrm{PH^{CH_3}}$, cf. Allender, Balaji, Datta, and Pratap).

  Of course, in this case an arbitrary language can be encoded by bits of a real number, and in particular, you can choose it NP-complete. See e.g. zinc_11010’s answer.

• If $n$ is in unary, then the bits of any real number form a sparse language. Thus, there is no NP-complete real number unless P = NP by Mahaney’s theorem.

Answer 2

It's not hard to make a contrived example based on SAT. I'm not aware of any "natural" examples, though.

Let $f$ be an injection from boolean formulas to the natural numbers given by mapping symbols in the formula to digits. Then construct the real number $x$ where the $n$th digit after the radix point is 1 iff $f^{-1}(n)$ exists and is a satisfiable boolean formula.

Then it is easy to see that $f$ implements the mapping reduction from SAT to the decision problem for $x$, showing that it is NP-hard. It is also in NP by reduction to SAT.

• Emil Jeřábek: You seem to assume that $n$ is given to the algorithm in binary. But this is at odds with the claim in the question that $e,ドル $\pi,ドル $\ln2,ドル etc. are computable in P.