Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

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,c)=\exists x\le c\\,\exists y\le c\\,(x^2=a+by)$ (due to Adleman and Manders). It is even consistent with the current state of knowledge that every NP predicate is definable by an $E_1$ formula (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 is $E_1$-definable.

Even if the general statement does not hold, 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.

share|improve this answer
    
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. –  M Carl Sep 5 '12 at 13:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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