Skip to main content
27 votes
Accepted

Deciding whether an interval contains a prime number

Disclaimer: I'm not an expert in number theory. Short answer: If you're willing to assume "reasonable number-theoretic conjectures", then we can tell whether there is a prime in the interval $[n, n+\...
Noah Stephens-Davidowitz's user avatar
19 votes
Accepted

Any computable transcendental number that is computable in P time but not $O(n)$

Here is the construction of such a number. You can argue whether this means such a number is "known". Take any function $f$ from $\mathbb{N}$ to $\{ 1, 2, \ldots, 8 \}$ where the $n$'th digit is not ...
Jeffrey Shallit's user avatar
11 votes

Any computable transcendental number that is computable in P time but not $O(n)$

More generally, for any constant $k\ge1$, there are transcendental numbers computable in polynomial time, but not in time $O(n^k)$. First, by the time hierarchy theorem, there exists a language $L_0\...
Emil Jeřábek's user avatar
9 votes

Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?

There are essentially only two algorithms that I'm aware of: Use repeated-squaring, along the lines you mentioned. Factor $n$ using a state-of-the-art algorithm, then use the Chinese remainder ...
D.W.'s user avatar
  • 12.2k
8 votes

Algorithm to check whether a given set is Sidon

Probably OP's problem has no sub-quadratic algorithm, as it is 3-SUM-hard, per [1]: Corollary 1.2 [1]. Under the 3-SUM hypothesis, for all $\delta > 0$, determining whether a given set of $n$ ...
Neal Young's user avatar
  • 10.8k
4 votes

The factoring problem reduces to order finding or is it the other way around?

Both! You may want to read the answers to this related question, and the 1987 paper of Heather Woll, Reductions among number theoretic problems, Information and Computation 72 (1987) 167-179 cited ...
Frédéric Grosshans's user avatar
4 votes

Algorithm to check whether a given set is Sidon

In what range are the values in your set $S$? Note that if the range is not too large you can represent $S$ by a polynomial $P_S$ ($P_S = \sum_{s \in S} x^s$) and compute $P_S^{2}$ with the FFT ...
Bernardo Subercaseaux's user avatar
3 votes

Analytic Number theory in TCS

Codes/Lattices are certain combinatorial objects that are commonly used within TCS. A basic question for both of them is finding "short" codewords/lattice points, known as the Minimum Distance problem/...
Mark Schultz-Wu's user avatar
3 votes
Accepted

Relation between transcendental numbers and computational complexity?

One other way to look at this, which brings in potentially all complexity classes above $\mathsf{E} = \mathsf{DTIME}(2^{O(n)})$, is to consider real numbers in their binary expansion. Any real number ...
Joshua Grochow's user avatar
2 votes

Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?

Using Fermat theorem, $a^p -a = 0 (\mod p) $ and if a and p are co-prime, then $ a^{p−1} − 1 =1(\mod p) $ So if u choose n to be a prime number(say p), then $a^{b^c} \mod p = a^{ (b^{c} \mod (p-1))} \...
Bhaskar13's user avatar
  • 129
2 votes

Using the de Bruijn sequence to find the $\lceil\log_2 v \rceil$ of an integer $v$

Where does this constant comes from? Quoting: "On December 10, 2009, Mark Dickinson shaved off a couple operations by requiring v be rounded up to one less than the next power of 2 rather than ...
FranG's user avatar
  • 21
2 votes

Is prime-counting function #P-complete?

Some heuristic evidence: to the best of our knowledge $\pi(n)$ looks like a simple function corrected by random fluctuations. Thus I’d expect a poly-time machine with a $\pi(n)$ oracle to be no ...
Geoffrey Irving's user avatar
1 vote
Accepted

Is modular square roots modulo primes in $NC$?

Square roots modulo $2^n$ can be computed in (uniform) $\mathrm{TC}^0$. More generally, just like in On parallel complexity of modular inverse, given $X$ and $M$ in binary and $b$ in unary such that $...
Emil Jeřábek's user avatar
1 vote

Difference Sets

"Beltway Reconstruction Problem” - arxiv.org/pdf/1212.2386.pdf may help. Note that you're asking for the function corresponding to $P$ whose autocorrelation is the given function corresponding to $A$. ...
Mark S's user avatar
  • 1,125

Only top scored, non community-wiki answers of a minimum length are eligible