7
$\begingroup$

Here, $E_1$ denotes the set of arithmetic formulas starting with a bounded existential quantifier, followed by a quantifier-free formula. Is there an $E_1$-formula $\phi$ such that $\phi(n)$ holds iff $n$ is prime? If yes, it is likely to be rather complicated to obtain, as this apparently implies that PRIMES is in P. Clearly, there is such a $U_1$-formula (i.e. one starting with a bounded universal quantifier instead). And of course there's this famous prime polynomial, but this gives a $\Sigma_1$-statement where the variables correspond to exponentiations and factorials, so certainly there can be no polynomial bounds for them.

$\endgroup$

1 Answer 1

10
$\begingroup$

I don’t see how an $E_1$ formula would give a polynomial-time algorithm. Primality testing has been known to be in NP long before AKS (due to Pratt), and this gives a definition of primes by a $\Sigma^b_1$ formula (a bounded existential quantifier followed by a formula with logarithmically bounded quantifiers); if we extend the language of arithmetic by sufficiently many polynomial-time computable functions, this becomes an $E_1$ formula.

Meanwhile, there are $E_1$ formulas in the basic language of arithmetic expressing some NP-complete predicates, such as $\phi(a,b)=\exists x\le b\,\exists y\le b\,(x^2+ay=b)$ (due to Adleman and Manders). It is even consistent with the current state of knowledge that every NP predicate $R(x)$ is definable by an $E_1$ formula where the bound on the quantifier is allowed to be $2^{(\log x)^c}$ for a constant $c$ (this is known as the “bounded Hilbert’s 10th problem”); there are some conjectures that imply that this is the case, but also some results indicating otherwise, see e.g. Pollett for a relevant discussion. Of course, a positive answer would in particular imply that primality definable in such a way. (Note that $E_1$ itself in the basic language of arithmetic is a strict subset of NP by the nondeterministic time-hierarchy theorem, as every $E_1$ predicate is computable in nondeterministic time $O(n^2)$, or even $O(n\log n)$ using the best known multiplication algorithms.)

Irrespective of general results like that, it is possible that Pratt’s (or another) NP definition of primality can be expressed as an $E_1$ formula, but as far as I am aware, this is unknown.

$\endgroup$
3
  • $\begingroup$ Right, what I thought to be an argument leading from an $E_1$-definition to a quick prime testing algorithm was simply due to my lack of knowledge about complexity theory. Thanks for the information on the problem, I'll check out the reference. $\endgroup$
    – M Carl
    Sep 5, 2012 at 13:02
  • $\begingroup$ @EmilJerabek I think in $\phi(a,b)$ formula $y\geq0$ holds or else the problem is in $\mathsf{P}$. $\endgroup$
    – Turbo
    Nov 27, 2020 at 13:51
  • $\begingroup$ The language of arithmetic only has variables ranging over the natural numbers. (Also, it would not make the slightest bit of sense to have "bounded" integer quantifiers that were actually unbounded from below.) $\endgroup$ Nov 27, 2020 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.