05-15-2018, 03:52 AM
(This post was last modified: 05-15-2018, 04:15 AM by Roger.
Edit Reason: typos, a parentetical comment
)
There are a couple of problems with the Algorithmica (i.e. P=NP) scenario from an OA point of view:
1) While it's not outside the bounds of things thought possible by some contemporary scientists, last time a survey was done the best guess of ~95% of mathematicians working in the area was that P < NP (this is for the worst case behavior, i.e. for Algorithmica -- the average case question i.e. Heuristica is much more of an open question).
2) The things that Algorithmica P=NP would let you do, if it were true, are pretty amazing, bordering on implausible to the average reader. It makes things very easy that most people would intuitively expect to be hard even for a transapient. It means that there is a single key algorithm that gives anyone with access to it a general way to save any case of some particular NP-complete problem (let's say it's the Traveling Salesman problem) in an amount of time that increases only polynomially with the size N of that case (for that problem, the number of cities). While 'polynomially' doesn't rule out the possibility that it would scale as N^100, in our experience so far most polynomial algorithms (once well optimized) tend to run as small powers like N, N^2, or N^3 -- which would mean that a cluster-brain could use it for astronomically large N, and even a computer run by a modosophont could handle N in the thousands or millions, so usefully large problems. Combined with simple methods for each other NP-complete problem for converting a case of that into a case of the Traveling Salesman problem that only increases N polynomially (generally already known now in 2018), that lets anyone with access to this key algorithm have the intellectual superpowers described above. Even if we assume that discovering or understanding this algorithm requires some specific level of transapience (say S3), it's very hard to explain why it couldn't just be turned into a library runnable on a modosophont's computer, say as part of their exoself -- just running the algorithm is going to involve pressing "go", not intricate translogic. I.e. it's ultratech, not transapientech or clarketech. Any modosophont with access to this then had no need to, for example, do mathematics: just wire the key algorithm up to simple automated formal proof checker that can distinguish a correct formal proof from an incorrect one (tech we have now), encode the structure of the mathematical theorem you want to prove and a desired proof size as an algorithm (basic programming work), convert that to an instance of the Traveling Salesman problem using a compiler (again, tech we have now), run the algorithm, and if any proof of the theorem no longer than the maximum size you asked for is possible, then the key algorithm will spit it out. If not (whether because your theorem is false, or because the shortest poof is longer, it won't -- and it won't tell you which): so if that happens, try again with a bigger maximum size and run the key algorithm longer or on more computronium, or try asking for a disproof of the theorem instead.
So most intellectual endeavors that people expect to require creativity and deep thought -- mathematics, engineering, logistics, basically anything where, given a solution, recognizing that it is in fact a solution could be automated -- then turn into a matter of creating an algorithmic description of your problem and how to recognize a solution if you;re handed one, recoding that algorithm as an (highly contrived) instance of the Traveling Salesman (using a compiler), then handing that to the key algorithm and then leaving it tio run until it spits out an answer, or fails to. No ingenuity or deep thought required -- if you can fully describe a problem, solving it becomes trivial, even for a modosophont.
That doesn't sound like OA to me: as ultratech goes, it's too good, and it makes the vast brooding hyperbrains look, well, redundant, at least as long as the key algorithm scales as N or N^2 or N^3. Or, if you decide "the key algorithm exists, but it's polynomial with O(N^10)" -- which is hard to justify -- then maybe modosophonts with access to some fast computronium can use it use it for N=10, S1's for N=33, and S6's can use it for N=10,000 -- in which case it's an amusing little toy with no practical application to any real-world problem of any significant size unless you're an archailect, or at least have access to an archailect-sized bank of computronium. (I'm assuming here that the key algorithm can be parallelized -- generally not the case for algorithms with high polynomial powers like O(N^10) -- otherwise what matters isn't how much computronium you have but how fast a small package of it runs -- assuming the algorithm requires say O(N^10) time but no worse than say O(N^2) space. If it also scales as O(N^10) in space you get much the same results as for parellelizing it, only now it's slow even on magmatter-based hardware.)
About the closest I can get to an OA feel is if you say that the running time or space requirement of the key algorithm is around O(N^5) -- so a modosophont can use it up to about N=100, an S1 up to maybe N=1,000 (still a bit short for most proofs -- they typically have more than a thousand symbols in them), and an S6 up to 100,000,000 (more than adequate for most proofs). However, this still leaves another problem from an OA point of view, since it doesn't suffer from toposophic barriers: if you're a modosophont with access to Von Neumann nanotech (i.e if you're not a prim or a ludd), then you can easily turn any unused gas giant into a simply organized bank of computronium (with no more sophisticated internal structure than a modosophont computer) and run the key algorithm just as well as an S4 can. You don't need to be an S3+ to have any hope of designing a J-brain usable for this algorithm.
So not only does P=NP automate intellectual creativity in a way that feels unintuitive to most SF readers, it does so in a way that manifestly doesn't suffer from toposophic barriers and would obviously be prebuilt into every superbright's exoself -- you end up with the fire of the gods available to everyone in convenient 2 litre bottles.
So I think we can rule out Arithmetica -- it makes for implausible stories that don't have an OA feel (the only SF author I know who explicitly assumes P=NP is Charles Stross in his Laundry Files novels, which really are indistinguishable from magic, and I'm not sure even he has fully thought through the consequences). That leaves Heuristica -- which as Implagliazzo describes it is almost as bad as Algorithmica, but as outlined above I believe can be saved -- or Pessiland, which is just dull, or Minicrypt or Cryptomania. Most modern readers are going to implicitly assume Cryptomania: public key encryption works, and if it were done correctly could actually keep out archailects if only they didn't have mechanical telepathy and thus didn't need to break your code to know what you are doing.
Would people like me to write this up as an attempted Encylopedia Galactica article? The most OA solution would probably be "The archailects assure us it's Cryptomania, but unfortunately the proof that P < NP for average case problems over realistic distributions for at least the majority of NP-complete problems is apparently comprehensible only to an S2, for some cases an S3, so we have to take their word for it, and these Omega Key things make us dubious, unless they're really just a package holding a tiny comm-wormhole to an S5 using technotelepathy"
1) While it's not outside the bounds of things thought possible by some contemporary scientists, last time a survey was done the best guess of ~95% of mathematicians working in the area was that P < NP (this is for the worst case behavior, i.e. for Algorithmica -- the average case question i.e. Heuristica is much more of an open question).
2) The things that Algorithmica P=NP would let you do, if it were true, are pretty amazing, bordering on implausible to the average reader. It makes things very easy that most people would intuitively expect to be hard even for a transapient. It means that there is a single key algorithm that gives anyone with access to it a general way to save any case of some particular NP-complete problem (let's say it's the Traveling Salesman problem) in an amount of time that increases only polynomially with the size N of that case (for that problem, the number of cities). While 'polynomially' doesn't rule out the possibility that it would scale as N^100, in our experience so far most polynomial algorithms (once well optimized) tend to run as small powers like N, N^2, or N^3 -- which would mean that a cluster-brain could use it for astronomically large N, and even a computer run by a modosophont could handle N in the thousands or millions, so usefully large problems. Combined with simple methods for each other NP-complete problem for converting a case of that into a case of the Traveling Salesman problem that only increases N polynomially (generally already known now in 2018), that lets anyone with access to this key algorithm have the intellectual superpowers described above. Even if we assume that discovering or understanding this algorithm requires some specific level of transapience (say S3), it's very hard to explain why it couldn't just be turned into a library runnable on a modosophont's computer, say as part of their exoself -- just running the algorithm is going to involve pressing "go", not intricate translogic. I.e. it's ultratech, not transapientech or clarketech. Any modosophont with access to this then had no need to, for example, do mathematics: just wire the key algorithm up to simple automated formal proof checker that can distinguish a correct formal proof from an incorrect one (tech we have now), encode the structure of the mathematical theorem you want to prove and a desired proof size as an algorithm (basic programming work), convert that to an instance of the Traveling Salesman problem using a compiler (again, tech we have now), run the algorithm, and if any proof of the theorem no longer than the maximum size you asked for is possible, then the key algorithm will spit it out. If not (whether because your theorem is false, or because the shortest poof is longer, it won't -- and it won't tell you which): so if that happens, try again with a bigger maximum size and run the key algorithm longer or on more computronium, or try asking for a disproof of the theorem instead.
So most intellectual endeavors that people expect to require creativity and deep thought -- mathematics, engineering, logistics, basically anything where, given a solution, recognizing that it is in fact a solution could be automated -- then turn into a matter of creating an algorithmic description of your problem and how to recognize a solution if you;re handed one, recoding that algorithm as an (highly contrived) instance of the Traveling Salesman (using a compiler), then handing that to the key algorithm and then leaving it tio run until it spits out an answer, or fails to. No ingenuity or deep thought required -- if you can fully describe a problem, solving it becomes trivial, even for a modosophont.
That doesn't sound like OA to me: as ultratech goes, it's too good, and it makes the vast brooding hyperbrains look, well, redundant, at least as long as the key algorithm scales as N or N^2 or N^3. Or, if you decide "the key algorithm exists, but it's polynomial with O(N^10)" -- which is hard to justify -- then maybe modosophonts with access to some fast computronium can use it use it for N=10, S1's for N=33, and S6's can use it for N=10,000 -- in which case it's an amusing little toy with no practical application to any real-world problem of any significant size unless you're an archailect, or at least have access to an archailect-sized bank of computronium. (I'm assuming here that the key algorithm can be parallelized -- generally not the case for algorithms with high polynomial powers like O(N^10) -- otherwise what matters isn't how much computronium you have but how fast a small package of it runs -- assuming the algorithm requires say O(N^10) time but no worse than say O(N^2) space. If it also scales as O(N^10) in space you get much the same results as for parellelizing it, only now it's slow even on magmatter-based hardware.)
About the closest I can get to an OA feel is if you say that the running time or space requirement of the key algorithm is around O(N^5) -- so a modosophont can use it up to about N=100, an S1 up to maybe N=1,000 (still a bit short for most proofs -- they typically have more than a thousand symbols in them), and an S6 up to 100,000,000 (more than adequate for most proofs). However, this still leaves another problem from an OA point of view, since it doesn't suffer from toposophic barriers: if you're a modosophont with access to Von Neumann nanotech (i.e if you're not a prim or a ludd), then you can easily turn any unused gas giant into a simply organized bank of computronium (with no more sophisticated internal structure than a modosophont computer) and run the key algorithm just as well as an S4 can. You don't need to be an S3+ to have any hope of designing a J-brain usable for this algorithm.
So not only does P=NP automate intellectual creativity in a way that feels unintuitive to most SF readers, it does so in a way that manifestly doesn't suffer from toposophic barriers and would obviously be prebuilt into every superbright's exoself -- you end up with the fire of the gods available to everyone in convenient 2 litre bottles.
So I think we can rule out Arithmetica -- it makes for implausible stories that don't have an OA feel (the only SF author I know who explicitly assumes P=NP is Charles Stross in his Laundry Files novels, which really are indistinguishable from magic, and I'm not sure even he has fully thought through the consequences). That leaves Heuristica -- which as Implagliazzo describes it is almost as bad as Algorithmica, but as outlined above I believe can be saved -- or Pessiland, which is just dull, or Minicrypt or Cryptomania. Most modern readers are going to implicitly assume Cryptomania: public key encryption works, and if it were done correctly could actually keep out archailects if only they didn't have mechanical telepathy and thus didn't need to break your code to know what you are doing.
Would people like me to write this up as an attempted Encylopedia Galactica article? The most OA solution would probably be "The archailects assure us it's Cryptomania, but unfortunately the proof that P < NP for average case problems over realistic distributions for at least the majority of NP-complete problems is apparently comprehensible only to an S2, for some cases an S3, so we have to take their word for it, and these Omega Key things make us dubious, unless they're really just a package holding a tiny comm-wormhole to an S5 using technotelepathy"