33
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^...
answered Oct 31 '12 at 11:40
Emil Jeřábek supports Monica
11.2k3 gold badges42 silver badges65 bronze badges
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 ...
22
An extended comment:
Collatz-like sequences can be computed by small Turing machines having few symbols and states. In "Small Turing machines and generalized busy beaver competition" by P. Michel (2004), there is a nice table that positions Collatz-like problems between decidable TMs (for which the halting problem is decidable) and Universal TMs.
There ...
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
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 ...
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
See Bach and Sorenson, Sieve algorithms for perfect power testing, Algorithmica 9 (1993), 313-328, DOI: 10.1007/BF01228507, and D. J. Bernstein, Detecting perfect powers in essentially linear time, Math. Comp. 67 (1998), 1253-1283.
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
Verifying whether $b \in \langle h_1, \ldots, h_n\rangle$ (where $h_i$ are vectors according to the OP's comments) is equivalent to verifying whether there is a solution to this system:
$$
\begin{pmatrix}
h_{1}(1) & \cdots & h_{n}(1) & d_1^{e_1} & 0 & \cdots & 0 \\\\
\vdots & \ddots & \vdots & \vdots & \vdots ...
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 happy to say that I think we can answer this question in the affirmative: that is, deciding whether a linear congruence is feasible modulo k is coModkL-complete.
We can actually reduce this problem to the special case of prime powers. One may show that:
Normal Form. The class coModkL consists of langauges L of the form L = Lp1 ∩&...
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
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.5k4 gold badges51 silver badges134 bronze badges
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 ...
6
This is a full answer to the problem which does not use Merlin at all.
Deléglise-Dusart-Roblot [1] give an algorithm which determines the number of primes up to $x$ that are congruent to $l$ modulo $k,$ in time $O(x^{2/3}/\log^2x).$ A modification of the algorithm of Lagarias-Odlyzko [2] allows the same to be computed in time $O(x^{1/2+o(1)}).$
Using ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
