For this post I will only count the operations PLUS, MINUS, MULT. They may be done on rather large numbers.
Recall that from the work coming out of Hilberts 10th problem we know the following: For every c.e. set (used to be called r.e., some people still do) there is a polynomial f in 13 or less variables (we'll assume 13) with coefficients in the integers such that
x in A iff (∃ a1,...,a13))[f(x,a1,...,a13)=0]
In an article about Hilbert's 10th problem written in 1974 by Davis-Matiyasevich-Robinson they note that by this result there is a FINITE number M such that, for ALL primes p, there is a certification that p is prime that uses at most M operations: given p a prime let a1,...,a13 be such that f(p,a1,...,a13)=0. The certification that p is prime is just the evaluation of that polynomial and seeing that its 0.
Is this still the only proof that one can certify primality in a CONSTANT number of operations?
Primes is irrelevant to all of this--- any c.e. set would work. (The result for c.e. sets may qualify as a theorem that is less interesting because its more interesting.) But for primes I am wondering if there is another way to do this- perhaps using number theory, perhaps with a smaller value of M. For the explicit poly for primes, due to Jones, see here.
There would be no reason to expect the "witness" (a1,...,a13) to have a number of bits that is polynomially related to the number of bits in "x", right?
ReplyDeleteCorrect- the numbers a1,...,a13 could be enormous.
DeleteSo good point- this does NOT give an alternative proof that
Primes is in NP.
I think that before Matiyasevich's result it was not known that there is a such a polynomial for the primes. So probably the case for the primes is not easier than the case for all r.e. sets.
ReplyDeleteThere may be something here to wonder about for complexity theory. Most people didn't believe that the r.e. sets are diophantine since that would have so many unlikely consequences, as e.g. that the primes are diophantine, none of which were believed to hold, and were far from being proved to hold. In fact, Matiyasevich's result came rather unexpected and was of the P=NP-type of resolving Hilbert's 10-th problem.
ReplyDeleteSol to H10 like if P=NP: YES, people thought it just so unlikel.
DeleteSol to H10 NOT like P=NP: Not that many people were thinking about it.
Was not widely regarded as an important problem.
but YES, this is a case where the conventional wisdom was wrong- a lesson for us all.
Are there really that many researchers working on the problem?
DeleteMy experience is that excluding GCT almost no-one works on a direct proof or disproof. If you add research towards proving the hypothesis of conditional result that would then give (usually) P <> NP , you'll get probably about 100 researchers or so.
Among logicians, the Matiyasevich result was not a surprise. There were several people working on it at the time, and the existing partial results of Julia Robinson were tantalizingly close. Martin Davis had even gone so far as to predict that some young Russian was going to complete the existing work (his point being that the end was in sight, but horribly tedious).
Delete