27
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+\Delta]$ in time $\mathrm{polylog}(n)$. If you're not willing to make such an assumption, then there is a beautiful algorithm due to Odlyzko that achieves $n^{1/...
21
($=$ 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 $|$, $+$, and $\le$:
$$\begin{align*}
\gcd(a,b)=c&\iff c\ge0\land c\mid a\land c\mid b\land\forall d\:(d\mid a\land d\mid b\to d\mid c)\\
&\iff c\ge0\land c\...
18
This problem has a variation with a single integer input:
Does $n$ have a divisor strictly in between its two largest prime
factors?
The idea is to use the same randomized reduction from subset sum described in the top answer to the linked question, but with the target range encoded as the largest two primes instead of given separately. The definition ...
18
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 real time; in other words, the TM must compute the n'th digit in n time.
Third, the result of Adamczewski et al. is only about finite automata and deterministic ...
17
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 https://dx.doi.org/10.1002%2Fcpa.3160390713), and if I remember correctly, there is now even a deterministic polynomial-time solution. But counting the number ...
17
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 no solution :-)
The counting version is #P-hard: Graham R. Brightwell, Peter Winkler:
Counting Eulerian Circuits is #P-Complete. ALENEX/ANALCO 2005: 259-262
14
First of all, there is a formal definition of "quantum-NC", see QNC on the zoo.
GCD is indeed a good candidate for a problem that could be shown to be in QNC, but it's not known to be in NC. However, finding a QNC algorithm for GCD is still an open problem.
The feeling for which this is believed to be true comes from the fact that the Quantum Fourier ...
11
We can show that if all $\alpha_i$ are different, then square removal and factoring of $n$ are equally hard.
It is obvious, that if we can factor $n$, we can also compute square removal of $n$.
The other direction is a bit more tricky. First compute the square removal of $n$ and let's call this $m$. From the definition it follows that $m$ divides $n$. ...
10
First note that this algorithm only computes $\lceil \log_2 v \rceil$, and as the code is written, it works only for $v$ that fit in a $32$-bit word.
The sequence of shifts and or-s that appears first has the function of propagating the leading 1-bit of $v$ all the way down to the least significant bit. Numerically, this gives you $2^{\lceil \log_2 v \rceil}...
10
I believe no polynomial algorithm is known.
According to a paper this is used in at least one cryptosystem:
Abstract. We propose a cryptosystem modulo $p^k q$ based on the RSA
cryptosystem. We choose an appropriate modulus $p^ k q$ which resists two
of the fastest factoring algorithms, namely the number field sieve and
the elliptic curve method.
...
10
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, the problem is still open. One direction of the implication is easy, of course.
9
I'm not sure this is a statement about primes so much as it is a statement about secret key generation: if the method is deterministic (e.g. take the smallest prime larger than 10^20), then your adversary can simply reproduce the computation to find your secret key.
9
See my paper with Eric Bach, "Factoring with cyclotomic polynomials", where we show that if the cyclotomic polynomial $\Phi_k(p)$ is $B$-smooth for any $p$ dividing $N$, then we can factor $N$ in time polynomial in $\log N$ and $k$ and $B$. In particular this gives a $(p+1)$-method (see the earlier work of Williams) and $(p^2+1)$ method.
http://www.ams.org/...
9
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 thoerem. If $p$ is prime, you can compute $a^{b^c} \bmod p$ efficiently by computing $b^c \bmod p-1$ using fast exponentiation, call the result $d$, then computing $...
9
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 Ouaknine, Antonia Lechner and Ben Worrell. A preprint is available here: https://www.cs.ox.ac.uk/people/james.worrell/LICS-main.pdf
According to the authors, the ...
8
TL;DR The decimal expansion of a fixed rational number is not pseudorandom in the cryptographic sense, but irrational numbers (are conjectured to) exhibit some weaker but interesting forms of pseudorandom behavior.
Roughly speaking, a sequence $s \in \{0, \ldots, B\}^n$ is pseudorandom with respect to distinguishers $\cal A$, if it cannot be distinguished (...
8
The textbook of Computational Complexity: Modern Approach, by Arora and Barak gives such example:
They define the decision problem Integer Factoring on input of three positive integers,
$\text{Integer Factoring} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$.
They state that Alon and Kilian showed that if ...
answered Jun 21 '13 at 17:07
Mohammad Al-Turkistany
20.3k4 gold badges56 silver badges142 bronze badges
8
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 have at least one linear extension
b) How many does it have? #P-complete to determine this (Brightwell and Winkler, Counting Linear Extensions, Order, 1991)
c) ...
7
Some comments (not really an answer). Let's classify 32-bit integers $c$ as follows:
Type X: $c$ (as a binary string) is De Bruijn sequence (for all rotations, bits [27,31] are distinct). An example:
11111011100110101100010100100000
Type Y: bits [27,31] of $2^i \cdot c$ are distinct for $i = 0, 1, ..., 31$. This is what Leiserson et al. uses. Examples:
...
7
Your problem seems a special case of the turnpike reconstruction problem (for which no polynomial time algorithm is known).
See for example: Shiteng Chen, Zhiyi Huang, and Sampath Kannan, "Reconstructing Numbers from Pairwise Function Values".
Abstract: The turnpike problem is one of the few natural problems
that are neither known to be NP-complete nor ...
7
Somewhat late in the day but the following paper by Allender, Saks, Shparlinski proves that (among other lower bounds) that GCD is not in $\mathsf{AC}^0$ or $\mathsf{AC}^0[p]$ for any prime $p$.
7
[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 uncomputable, that's some kind of weak evidence that there's no "regular-ish" formula for primality. (I mean, we know the set of primes itself is not regular, but ...
6
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 check if your formula is empty or not) but the counting problem is #P-hard. Even approximating the number of satisfying assignments of such formula is hard (see ...
6
(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 space using sums of logarithms. In more detail, the algorithm is as follows:
Using binary counters, count the numbers of occurrences of each possible input ...
6
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 infinitely many vectors $(a_0,\dots,a_n)\in\mathbb Z^{n+1}$, and this holds even you fix all but two of the $a_0,\dots,a_n$ in advance.
5
Update: The description below is for a different problem (in which you have all pairwise distances in a set rather than pairwise distances between two distinct sets). I'll leave it up anyway since it is closely related.
This problem is called the beltway problem, and is a special case of the general $d$-torus embedding problem. It is also closely related to ...
5
There have been interesting developments on this problem, however Replacing $AC^0$ with ACC(2) (Namely allowing mod 2 gates as well) is still well out-of-reach. Some progress beyond Ben Green's theorem can be found in this MO question https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function as well as this one https://...
5
Consider the function $T: \mathbb N \rightarrow \mathbb N$, where $T(n)=n/2$ when $n$ is even and $T(n)=n+1$ when $n$ is odd. Then it is known that for any $n \in \mathbb N$, there exists a $k \in \mathbb N$ such that $T^{(k)}(n)=1$.
If instead of $T(n)=n+1$ when $n$ is odd, we had defined $T(n)=3n+1$ when $n$ is odd, we would have the Collatz Conjecture, ...
5
Terry Tao's answer on MathOverflow.
5
Added later: As noted in the comments, the NP upper bound is trivial if a, b, and c are positive, as was asked.
Theorem 1.2 in this paper shows that deciding if a given diophantine equation in two variables has a solution is in NP.
Only top voted, non community-wiki answers of a minimum length are eligible
