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+\...
- 1,214
21
votes
Accepted
Decidability of diophantine equations over {=, +, gcd}
($=$ is a logical symbol, hence I will not write it as part of the signature.) The satisfiability problem is decidable, as $\gcd$ has both a universal and an existential definition in terms of $|$, $+$...
- 18.6k
18
votes
Accepted
Is Hartmanis-Stearns conjecture settled by this article?
First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn".
Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in ...
- 6,985
17
votes
Easy problems with hard counting versions
A very nice and simple example from Graph Theory is counting the number of Eularian circuits in an undirected graph.
The decision version is easy (... and the Seven Bridges of Königsberg problem has ...
- 23.2k
17
votes
Easy problems with hard counting versions
One interesting example from number theory is expressing a positive integer as a sum of four squares. This can be done relatively easily in random polynomial time (see my 1986 article with Rabin at ...
- 6,985
10
votes
Base-k representations of the co-domain of a polynomial - is it context-free?
Of course $k \geq 2$ here.
There once was a manuscript by Horváth that claimed to solve the problem, but it was unclear in several places and to my knowledge was never published.
As far as I know, ...
- 6,985
9
votes
Accepted
Easy problems with hard counting versions
Here's a truly excellent example (I may be biased).
Given a partially ordered set:
a) does it have a linear extension (i.e., a total order compatible with the partial order)? Trivial: All posets ...
- 342
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 ...
- 12.4k
9
votes
Decidability of diophantine equations over {=, +, gcd}
A something that might be too long for a comment, based on the previous answer by Emil.
In the case you are interested in the complexity of such a logic, consider reading LICS'2015 paper by Joël ...
- 1,422
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$ ...
- 10.9k
7
votes
Formalizing the "no formula for primes" intuition
[Certainly not a complete answer, but too long for a comment]
Testing whether a given DFA accepts the base-2 representation of at least one prime number is not known to be computable. If it were ...
- 38.5k
6
votes
Accepted
What is a known sequence for which being constant is not provable?
Let $T$ be a reasonble theory of arithmetic, say $\mathrm{PA}$. Consider the sequence
$$f(m) =
\begin{cases}
1 & \text{if $m$ encodes a proof of $\vdash_T 0 = 1$} \\
0 & \text{otherwise}
\end{...
- 29.5k
6
votes
Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?
This is impossible. No finite number of bits of $f(a_0,\dots,a_n)$ suffices to determine any of $a_0,\dots,a_n$; in fact, any nondegenerate real interval contains the values $f(a_0,\dots,a_n)$ for ...
- 18.6k
6
votes
Accepted
Comparing two products of lists of integers?
(I understand the description of the problem so that the input numbers are bounded by a constant, so I will not track dependence on the bound.)
The problem is solvable in linear time and logarithmic ...
- 18.6k
6
votes
Easy problems with hard counting versions
Concerning your second question, problems such as Monotone-2-SAT (deciding of the satisfiability of a CNF-formula having at most 2 positive literals by clause) is completely trivial (you just have to ...
- 2,344
5
votes
Easy problems with hard counting versions
From [Kayal, CCC 2009]: Explicitly evaluating annihilating polynomials at some point
From the abstract: ``This is the only natural computational problem where
determining the existence of an object (...
- 6,051
5
votes
Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?
If you know that the $a_i$'s are all not too large, and you have a good approximation to $f(a_0,\dots,a_n)$, I think LLL lattice basis reduction could be applicable (I haven't tried to verify the ...
- 12.4k
5
votes
Accepted
Complexity of counting integer roots of multivariate polynomials in a polyhedron?
The decision version of this problem is obviously in $\mathsf{NP}$, and Manders & Adleman showed that a specific case is NP-complete. Namely, even deciding whether there exists an integer $x \in [...
- 38.5k
5
votes
Accepted
Time complexity of square root floor
As mentioned in any number of basic sources (e.g., Wikipedia), $\lfloor\sqrt a\rfloor$ can be computed in time $O(M(n))$ using Newton iteration, where $n=\log a$ is the length of the input, and $M(n)$ ...
- 18.6k
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 ...
4
votes
Accepted
Logspace computation of Zeckendorf representation
Conversion from binary to the Zeckendorf representation can be done in uniform $\def\tc{\mathrm{TC}^0}\tc$, and a fortiori in logspace.
To fix notation, the Zeckendorf representation of a natural ...
- 18.6k
3
votes
Base-k representations of the co-domain of a polynomial - is it context-free?
I think I have a proof. The proof follows from this lemma.
Lemma. For a context-free language $L$ if for infinitely many $n$ there are $n^6$ words of equal length whose first $n^2$ letters are the ...
- 14.2k
3
votes
Base-k representations of the co-domain of a polynomial - is it context-free?
This is a sketch of the proof for $k=2$ and $L = \{[n^2]_2 \mid n \geq 1\}$; where $[n^2]_2$ is the binary representation of $n^2$. For better clarity we place the least significant bit of the binary ...
- 23.2k
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/...
- 978
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 ...
- 38.5k
2
votes
Is there a natural problem on the naturals that is NP-complete?
Our FOCS'17 paper on the Short Presburger Arithmetic is an example of a "natural" problem which is NP-c, and uses a constant number $C$ of integers in the input, say $C< 220$. It is different from ...
- 812
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 ...
- 21
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))} \...
- 129
2
votes
Accepted
Does this pairwise independent random process have expected max load $\sqrt{n}$?
The hash family you give has expected max load $\tilde{O}(n^{1/3})$, as shown in this recent paper:
Mathias Bæk Tejs Knudsen, "Linear Hashing is Awesome"
- 1,685
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 ...
- 3,313
Only top scored, non community-wiki answers of a minimum length are eligible