05-14-2018, 09:33 PM
Hi everyone. I've been reading Orion's Arm avidly for several years, and decided it was getting to the point where I should contribute.
I have a number of ideas for contributions; however, most of them fall into the category of "What happens next?", i.e. they're set after 10,600 A.T (some only a few centuries after, others up to a couple of millennia after). I assume this question will have come up before, and I'm guessing there's an official policy on it -- if so, where would I find that? Are people open to gradually (or at some point) pushing the date forward and writing post-10,600 material (either by revising the Encyclopedia to update it to a later data, or maybe in a separate section)? Or is there a policy that this will never happen?
On a pre-10,600 topic, what is the Orion's Arm position on P!=NP or P=NP? To add a little more detail, of the five currently-considered-plausible worlds outlined in https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf which one is canonical for OA? If it was the Algorithmica (i.e P=NP), or the uniform Heuristica scenario as described there (i.e. P ~= NP in practically all cases that you're likely to ever care about), then transapients should be able to efficiently do even more astounding things than they are seen doing in Orion's Arm: like trivially prove anything that can be proven, or optimize anything, or trivially crack any code -- and it's unclear why they'd need astronomical amounts of computronium to do it, since under this scenario generating any proof isn't significantly harder than checking a proof, finding the optimal solution to any set of constraints isn't much harder than measuring how optimal it is, and cracking any code isn't much harder than decrypting it with the key; so I think those would break the setting. Modosophonts and apparently even low transapients in OA are still using encryption (I haven't seen anything explicit about whether this includes public key encryption or indistinguishability obfuscation), so presumably the modosophonts believe (or hope) it's the Minicrypt or Cryptomania scenarios. But the existence of Omega Keys (unless those work by timing attacks, breaking software security, messing with the opponent's pseodorandom number generation, access to some sort of PSPACE Tipler oracle based on closed timelike curves, or something else other than polynomial time cryptoanalysis) suggests they might be wrong. I'm wondering if it's actually a variant of Heuristica (not described in the paper, but I believe actually a possibility) where instances of certain NP-complete problems drawn from certain distributions can on average be solved efficiently, and (most) others can't. I believe this is possible, since the "all NP-complete problems are polynomially equivalent to each other" tricks works only on worst case running time, not on average case running time for a specified distribution, since the mappings between them will generally transform an 'average' (for some distribution) instance of one NP-complete problem into a very contrived and non-typical instance of another (i.e. to a very contrived and artifical looking distribution that only produces instances in a subset of measure tending to 0 on the problem space). So there might be some distributions over the space of instances of some NP-complete problems where a typical case can be polynomially solved by an S0, others that can only be polynomially solved by algorithms that are only comprehensible to an S1 (through an S0 could 'turn the handle' on an algorithm that they had been given by an S1 but which made no sense to them -- this is transapientech, not clarktech), others that needed an S2, and so forth. There are thousands of different NP-complete problems already known (and doubtless many more by the OA period), each with many possible distributions across their problem space, so the landscape of what progressively became possible and what still wasn't possible at each S-level could be extremely complex. Still, if too many things become possible at S6, you get back to the problem described above with the generic Heuristica where just about everything is possible, that it gives the archailects what feels like intellectual superpowers, and I suspect would break the OA setting. So we would need that even at S6, the majority of distributions likely to come up in practical instances over the majority of NP-complete problems likely to come up in practical instances should be unsolvable.
What I'm less sure is what that possibility would mean for the existence of one-way functions as needed for encryption -- obviously if a purportedly one-way function was based on an NP-complete problem for which the average case was not solvable by an algorithm designable by or comprehensible to an S0, but was solvable by an S2-comprehensible algorithm, and if this fact (that the average case could be solved, as opposed to how to solve it) was also not provable by an S0, then a) it's not really a one-way function, but the S0 won't know this unless someone higher toposophic tells them, and b) you'd have a cryptosystem based on it that an S0 might be willing (if suitably memed) to use and no S0 could crack but an S2 could crack -- which would produce an effect a lot like that described in OA under Omega keys and Omega encryption. However, that paper references another paper by Levin https://arxiv.org/pdf/cs/0012023.pdf that claims to describe a 'complete' one-way function -- a function that is guaranteed to be one-way of any function is (admittedly, this function seems to be a Turing machine lightly disguised as a tile-matching problem, running some mix of other problems -- I'm unclear on how it improves over 'compose all possible candidate one-way functions, and if any of them are then the result is', and I'm also not clear whether the corresponding cryptosystem would be workable, but then I'm not a computational complexity expert or a cryptographer). So that suggests that even an S0.3 can design an optimal one-way-function, uninvertible even by an S6 if anything is uninvertible by an S6. Given that, and careful automated proof checking of the relevant cryptographic propocols, and S0 might be able to build an Omega-7 code. So tricking modosophonts into using not-really-but-apparently-one-way functions might be hard.
Also, if it's true that most 'common' distributions across most 'common' NP-complete problems are on average not soluble even by an S6 (as suggested above in order to avoid the disadvantages of 'generic Heuristica'), then that suggests that stumbling at random across a one-way function strong enough for an Omega7+ code is easy, and if you compose enough apparently-to-an-S0-one-way functions in series the odds are good that at least one of them really is one-way even against an S6 (so the combination of them is). Which (in the absence of active meming that's working even on Cyberians) suggests that modosophonts should generally have Omega-7+-grade encryption systems that are unbreakable to an S6 (assuming that the key size is big enough, which is pretty easy to get right). Which suggests that the Omega keys do something otehr than just crypto-algorithm cracking in polynomial time. In which case we might as well just put OA in Minicrypt or Cryptomania.
I have a number of ideas for contributions; however, most of them fall into the category of "What happens next?", i.e. they're set after 10,600 A.T (some only a few centuries after, others up to a couple of millennia after). I assume this question will have come up before, and I'm guessing there's an official policy on it -- if so, where would I find that? Are people open to gradually (or at some point) pushing the date forward and writing post-10,600 material (either by revising the Encyclopedia to update it to a later data, or maybe in a separate section)? Or is there a policy that this will never happen?
On a pre-10,600 topic, what is the Orion's Arm position on P!=NP or P=NP? To add a little more detail, of the five currently-considered-plausible worlds outlined in https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf which one is canonical for OA? If it was the Algorithmica (i.e P=NP), or the uniform Heuristica scenario as described there (i.e. P ~= NP in practically all cases that you're likely to ever care about), then transapients should be able to efficiently do even more astounding things than they are seen doing in Orion's Arm: like trivially prove anything that can be proven, or optimize anything, or trivially crack any code -- and it's unclear why they'd need astronomical amounts of computronium to do it, since under this scenario generating any proof isn't significantly harder than checking a proof, finding the optimal solution to any set of constraints isn't much harder than measuring how optimal it is, and cracking any code isn't much harder than decrypting it with the key; so I think those would break the setting. Modosophonts and apparently even low transapients in OA are still using encryption (I haven't seen anything explicit about whether this includes public key encryption or indistinguishability obfuscation), so presumably the modosophonts believe (or hope) it's the Minicrypt or Cryptomania scenarios. But the existence of Omega Keys (unless those work by timing attacks, breaking software security, messing with the opponent's pseodorandom number generation, access to some sort of PSPACE Tipler oracle based on closed timelike curves, or something else other than polynomial time cryptoanalysis) suggests they might be wrong. I'm wondering if it's actually a variant of Heuristica (not described in the paper, but I believe actually a possibility) where instances of certain NP-complete problems drawn from certain distributions can on average be solved efficiently, and (most) others can't. I believe this is possible, since the "all NP-complete problems are polynomially equivalent to each other" tricks works only on worst case running time, not on average case running time for a specified distribution, since the mappings between them will generally transform an 'average' (for some distribution) instance of one NP-complete problem into a very contrived and non-typical instance of another (i.e. to a very contrived and artifical looking distribution that only produces instances in a subset of measure tending to 0 on the problem space). So there might be some distributions over the space of instances of some NP-complete problems where a typical case can be polynomially solved by an S0, others that can only be polynomially solved by algorithms that are only comprehensible to an S1 (through an S0 could 'turn the handle' on an algorithm that they had been given by an S1 but which made no sense to them -- this is transapientech, not clarktech), others that needed an S2, and so forth. There are thousands of different NP-complete problems already known (and doubtless many more by the OA period), each with many possible distributions across their problem space, so the landscape of what progressively became possible and what still wasn't possible at each S-level could be extremely complex. Still, if too many things become possible at S6, you get back to the problem described above with the generic Heuristica where just about everything is possible, that it gives the archailects what feels like intellectual superpowers, and I suspect would break the OA setting. So we would need that even at S6, the majority of distributions likely to come up in practical instances over the majority of NP-complete problems likely to come up in practical instances should be unsolvable.
What I'm less sure is what that possibility would mean for the existence of one-way functions as needed for encryption -- obviously if a purportedly one-way function was based on an NP-complete problem for which the average case was not solvable by an algorithm designable by or comprehensible to an S0, but was solvable by an S2-comprehensible algorithm, and if this fact (that the average case could be solved, as opposed to how to solve it) was also not provable by an S0, then a) it's not really a one-way function, but the S0 won't know this unless someone higher toposophic tells them, and b) you'd have a cryptosystem based on it that an S0 might be willing (if suitably memed) to use and no S0 could crack but an S2 could crack -- which would produce an effect a lot like that described in OA under Omega keys and Omega encryption. However, that paper references another paper by Levin https://arxiv.org/pdf/cs/0012023.pdf that claims to describe a 'complete' one-way function -- a function that is guaranteed to be one-way of any function is (admittedly, this function seems to be a Turing machine lightly disguised as a tile-matching problem, running some mix of other problems -- I'm unclear on how it improves over 'compose all possible candidate one-way functions, and if any of them are then the result is', and I'm also not clear whether the corresponding cryptosystem would be workable, but then I'm not a computational complexity expert or a cryptographer). So that suggests that even an S0.3 can design an optimal one-way-function, uninvertible even by an S6 if anything is uninvertible by an S6. Given that, and careful automated proof checking of the relevant cryptographic propocols, and S0 might be able to build an Omega-7 code. So tricking modosophonts into using not-really-but-apparently-one-way functions might be hard.
Also, if it's true that most 'common' distributions across most 'common' NP-complete problems are on average not soluble even by an S6 (as suggested above in order to avoid the disadvantages of 'generic Heuristica'), then that suggests that stumbling at random across a one-way function strong enough for an Omega7+ code is easy, and if you compose enough apparently-to-an-S0-one-way functions in series the odds are good that at least one of them really is one-way even against an S6 (so the combination of them is). Which (in the absence of active meming that's working even on Cyberians) suggests that modosophonts should generally have Omega-7+-grade encryption systems that are unbreakable to an S6 (assuming that the key size is big enough, which is pretty easy to get right). Which suggests that the Omega keys do something otehr than just crypto-algorithm cracking in polynomial time. In which case we might as well just put OA in Minicrypt or Cryptomania.