3 ms·

Interesting article. The information quoted in the last paragraph contains an error. It seems that Adam Spencer confused a primality test for a factorization al

• bo1024 12y ago
  And that's a pretty cool-mindblowing idea -- we can "efficiently" prove that a number is composite, while still having no idea what its factors are!
  • zeroonetwothree 12y ago
    It's common in math to get theorems that prove existence without giving any explicit examples (nonconstructive proofs). A big research area is coming up with efficient ways to construct such examples.
    • bo1024 12y ago
      Definitely true, but these things are of a different "kind" (in my opinion). Often such a proof implies, for instance, a really inefficient algorithm, such as "try all the random possibilities and with positive probability such an example exists. They also tend to have a flavor of a somewhat complicated object whose existence you are proving, and they don't tend to be phrased as algorithms (especially not efficient ones). Here the primality test algorithm is an efficient algorithm, and doesn't seem natural to view as an existence/nonexistence proof of an object, in the same way. Instead it's exploiting the number-theoretic properties of primality in a weird way. Hope that makes sense, but anyway just trying to explain my intuition for why this is very different from the phenomenon you mentioned.