34
Based on the discussion, I’ll repost this as an answer.
As proved by Manders and Adleman, the following problem is NP-complete: given natural numbers $a,b,c$, determine whether there exists a natural number $x\le c$ such that $x^2\equiv a\pmod b$.
The problem can be equivalently stated as follows: given $b,c\in\mathbb N$, determine whether the quadratic $x^...
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/...
25
Bhatnagar, Gopalan, and Lipton show that, assuming the abc conjecture, there are polynomials of degree $O((kn)^{1/2+\varepsilon})$ representing the Threshold-of-$k$ function over ${\mathbb Z}_6$. For fixed constant $k$, and $m$ which has $t$ prime factors, the abc conjecture implies a polynomial for Threshold-of-$k$ over $\mathbb Z_m$ with degree $O(n^{1/t+\...
22
this paper points out that computing the reciprocal square root value using floating point representation is widespread in CS applications ("very common in scientific computations"); the authors show that a more efficient formula is possible for computing the correctly rounded value if the ABC conjecture holds.
[1] The abc conjecture and correctly rounded ...
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
16
This isn't my answer, but Terrence Tao gave a beautiful answer to this question on MathOverflow.
Here are the first few lines of his answer. To read the complete answer, follow the link.
There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n ...
15
The following answer was originally posted as a comment on Gil's blog
(1) Let $K=\mathbb{Q}(\alpha)$ be a number field, where we assume $\alpha$ has a monic minimal polynomial $f\in\mathbb{Z}[x]$. One can then represent elements of the ring of integers $\mathcal{O}_K$ as polynomials in $\alpha$ or in terms of an integral basis -- the two are equivalent.
...
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
Here's a $\text{NEXP}$-complete problem with a single natural number as the input.
The problem is about tiling an $n \times n$ grid with a fixed set of tiles and constraints on adjacent tiles and tiles on the boundary. All of this is part of the specification of the problem; it is not part of the input. The input is only the number $n$. The problem is $\...
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
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}...
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/...
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
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
A partial answer is that for even $k$ such a labeling does not exist.
For a set of $t$ disjoint subsets $S_1, \ldots, S_{t}$ (of size $n/k$, let $f(S_1, \ldots, S_t)$ denote the sum of their values).
Claim: if $t < k$ and $S_1 \cup \ldots \cup S_t \ne S'_1 \cup \ldots \cup S'_t$ then $f(S_1, \ldots, S_t) \ne f(S'_1, \ldots, S'_t)$.
To see why the claim ...
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
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
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
19.9k4 gold badges54 silver badges136 bronze badges
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 ...
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
As mentioned by Daniel, you can find some informations in the book A Course in Computational Algebraic Number Theory (link).
In particular, there are several ways of representing elements of number fields. Let $K=Q[\xi]/\langle\varphi\rangle$ be a number field with $\varphi$ a degree-$n$ monic irreducible polynomial of $\mathbb Z[\xi]$. Let $\theta$ be any ...
5
Start by putting $A$ into Jordan normal form, i.e., write $A=PJP^{-1}$ where $J$ is the Jordan normal form and $P$ is a suitably chosen invertible matrix. Then $A^k = PJ^k P^{-1}$, so without loss of generality I only need to consider possibilities for $A$ that are already in Jordan normal form.
For $2\times 2$ matrices, there are only three interesting ...
Only top voted, non community-wiki answers of a minimum length are eligible
