2 ms·
Of course, for all we know factorization is in P or even NC (as the GP notes, we don’t really have proofs). I’m more hopeful we will find a proof of P!=NC or P!
by amirhirsch 8y ago
Of course, for all we know factorization is in P or even NC (as the GP notes, we don’t really have proofs). I’m more hopeful we will find a proof of P!=NC or P!=NP than there being a quantum computer that beats RSA2048 in 21 years.
It aught to be lower-hanging-fruit to prove that factorization is not in NC (polylog depth, polynomial component circuit) and therefore NC!=NP => (P!=NP or NC!=P) so at least one of the two probably true statements is true...