The Complexity of Mathematics

EasyChair Preprint no. 3062, version history

VersionDatePagesVersion notes
1March 29, 202013
2April 20, 20206

I have submitted a new version of Preprint 3062 (The Complexity of Mathematics) as an extension of the older version. Certainly, in this version we found another way to prove the problem PRIMES is not in 1NSPACE(S(n)) for all S(n). The previous version was flawed in this proof. In this way, the proof of Riemann hypothesis and Goldbach's conjecture are still valid according to the older version, because they are supported in that previous proof in the same way. Indeed, we found the other problems exposed in the older version have not a strong proof. For that reason, they were removed from this new version.

3June 4, 20207

I added some missing arguments that the proofs needed in order to be correct.

4June 7, 20207

I have assumed in the previous version that the Goldbach's conjecture were true, because this won't have an infinite number of counterexamples. However, this assumption  have not been precisely proved yet. For that reason, we removed and changed the abstract and content of the paper.

5June 8, 20207

I have improved the Theorems 4 and 7 just remarking there are only two options, that is, our target language could be regular or non-regular and its complement is infinite or  is equal to the empty set.

6June 10, 20206

We changed 1NSPACE by NSPACE and used the complement instead of the original language. For that purpose, we have changed the abstracts, the keywords and the content of the paper.

7June 10, 20206

We state there are only three options: coL is equal to the empty set or coL in REG or coL is non-regular and coL is infinite, but the true statement should be: coL is equal to the empty set or coL in REG and coL is not empty or coL is non-regular and coL is infinite.

8June 11, 20206

We restate the Goldbach's conjecture to true again.

9June 11, 20207

I realize the infinite number of counterexamples in the Goldbach conjecture is possible when this set is sparse. In this way, we come back to the argument of previous version. We added a Conclusions section in this version.

10June 11, 20207

I have stated the Robin's inequality is always true on p for every prime number p, but I didn't specify that must be for every prime number p greater than 10. This is fixed in this version.

Keyphrases: complexity classes, Conjecture, number theory, primes, reduction, regular languages