Timeline for Philosophical Question related to Largest Known Primes
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 27, 2011 at 6:11 | comment | added | Gil Kalai | Certainly complexity theoretic definitions of that kind are nice and quite useful. (BTW, as far as I am concerned to know something with probability very close to 1 is "really" to know.) The opinion that once you show that a certain human activity represents an effort in P means that it is "trivialized" is a bit too far since it is quite plausible that all human activities represent efforts in P. | |
| Apr 26, 2011 at 23:49 | comment | added | Scott Aaronson | Gil (con't): I understand your counterargument, that we have several plausible such functions today, just no proof that they work (i.e., that they output an n-digit prime number in poly(n) time). But according to my criterion, such a proof is part of what it <i>means</i> to "know" a prime---and absent such a proof, one can indeed say that the largest "known" primes are those found by the Mersenne-hunters. Anyway, as I said, this definition is simply the best I could find---if you don't like it, feel free to propose an alternative! | |
| Apr 26, 2011 at 22:25 | comment | added | Scott Aaronson | Gil: My argument was that such a function would "trivialize" large prime contests in the following sense. For any n, I could tell you: "here's an algorithm that's GUARANTEED to output a specific n-digit prime number, using only polynomially more time than it takes to write the number down." So, at least from a complexity standpoint, a "largest prime contest" would start to look like a "largest power of 2 contest." | |
| Apr 26, 2011 at 20:23 | comment | added | Mikola | @Charles: I don't know if he just fixed this or not, but in the way it is currently written the running time is a function of the number of digits of $p$, not the digits of the input to the generator so your example is incorrect. | |
| Apr 26, 2011 at 18:58 | comment | added | Gil Kalai | In any case, the type of formula the OP asked about seems stronger than just "computable by a polynomial algorithm". Although CC may be applied to give a definition. The hypothetical example in the question you have an n digit prime by log*(n) arithmetic operations (exponentiation included). this looks like a rather low complexity... | |
| Apr 26, 2011 at 18:54 | comment | added | Gil Kalai | Scott, if we except your definition then we have a "function that generates primes" both under standard ulra difficult number theory conjectures (Cramer's conjecture) but also under strong derandomization conjectures from CC. I do not see why it trivializes largest primes contests. | |
| Apr 26, 2011 at 18:51 | comment | added | Charles | What about f(x) = the smallest prime greater than lg x? Sieving the numbers between lg x and 2 lg x takes polynomial time, but I wouldn't say that we 'know' f(2^(10^(10^10000))). | |
| Apr 25, 2011 at 23:14 | history | edited | Scott Aaronson | CC BY-SA 3.0 |
knowability --> known-ness
|
| Apr 25, 2011 at 22:16 | history | edited | Scott Aaronson | CC BY-SA 3.0 |
added 7 characters in body
|
| Apr 25, 2011 at 20:24 | history | answered | Scott Aaronson | CC BY-SA 3.0 |