Yeah, so this is a good point. The separation given by Grover’s algorithm is essentially a blackbox model. And Shore’s algorithm being better depends on the claim that factoring is not in P, which is a claim strictly stronger than P != NP (and a claim which is doubted by a lot more people. Henry Cohn for example says there’s no good reason to think that factoring is not in P.) So yes, this is under the black box. system.
There’s significant support not for that per se but that there’s no good reason to think otherwise. I don’t know for example what estimate Henry Cohn would give for a polynomial time factoring algorithm but in conversations (and in at least one talk he gave) he’s pointed out that there’s no complexity theoretic reason to suspect that factoring is tough. Moreover, there’s a polynomial time factoring algorithm for Q[x] where Q is the rationals (if you don’t care about units). The argument for factoring being hard boils down solely to “lots of people have worked on this and haven’t succeeded.” But that’s a very weak argument especially when one looks at how much progress has been made in factoring in the last few years (see especially the number field sieve and elliptic curve sieve). This is in contrast to say the conjectures that P != NP and BPP = P where in order for them to be wrong various things need to happen that seem unlikely.
But normally, problems eventually found to be in P are first found to be in BPP (primality testing being the most prominent example). Shouldn’t there at least be some probabilistic factoring algorithms (whatever that would mean)?
Also, in the likely event that P != NP, that would imply the existence of NP-intermediate problems, and factoring is a good candidate for being in such a class.
(Personally, my hunch is that factoring is indeed in P, but I’m far from qualified to have a lot of confidence in that.)
But normally, problems eventually found to be in P are first found to be in BPP (primality testing being the most prominent example). Shouldn’t there at least be some probabilistic factoring algorithms (whatever that would mean)?
This is an example where moving between a decision problem (returning a yes or no answer) and a function problem (returning a number or list of numbers) may break down. To make factoring equivalent to a decision problem one instead asks the question “Given n, and given a and b, is there are prime factor of n which is between a and b?” If one has a factorization of n one can answer this question quickly. If one has an oracle that can answer this question then one can factor in polynomial time by using a binary search tree of the intervals under n. This allows one to iterate calls to the oracle to find a prime factor in log_2 n time. Each time you find a prime factor p, you store it and then do the same process for n/p. This takes at most (log2 n) times the number of prime factors of n. In general, if calls to your oracle take time f(n), the whole thing takes at most f(n) (log2 n)^2 time. (You can actually do slightly better than that but this is good enough for pretty much all purposes.)
What I’m not sure about is whether the equivalent problem in BPP goes through. Say one has an oracle that answers the interval question with a BPP-like answer. Is there some way to turn that into a process that returns the correct factorization quickly with high probability? That’s not obvious to me. I haven’t really thought about the question that hard.
Also, in the likely event that P != NP, that would imply the existence of NP-intermediate problems, and factoring is a good candidate for being in such a class.
Right. That and and graph isomorphism seem to be the two most common natural problems that are potentially in that intermediate class.
Personally, my hunch is that factoring is indeed in P, but I’m far from qualified to have a lot of confidence in that.
I think you’d be in an extreme minority here. Even people like Henry who think that the evidence for factoring not being in P is small don’t seem to think it is actually in P. If I had to make a guess on the chance that factoring is in P, I’d probably put it at under 20%.
Right. That and and graph isomorphism seem to be the two most common natural problems that are potentially in that intermediate class.
Yes, but I thought there’s much higher confidence that graph isomorphism will be de-randomized, given how hard it is to even find problem instances that are unresolved after a few simple checks (e.g. of invariants of the adjacency matrices).
Yes, graph isomorphism looks a lot more likely to drop straight into P.
Not only is it hard to find difficult problem instances, for almost any nice type of graph (e.g. planar graphs, or interval graphs) there’s a polynomial time algorithm. On the other hand, there about as many specific types of graphs where one can show that being able to solve graph isomorphism for that type of graph means you can solve it for all graphs. Connected graphs are a trivial example but regular graphs are a less trivial example. But the closest rough equivalents for factorization look tough. Primality testing is easy, and testing if n=p^k for some prime is about as easy. But in those cases if the answer is “no” then you can’t factor it easily! And almost any other natural set of integers has factoring be really tough. For example, consider Fermat and Mersenne numbers. In both cases, while factorization does seem to be easier it isn’t that much easier. One can object that these are defined in part in an additive fashion, but this doesn’t help since the most obvious multiplicative set of nice numbers, products of two primes, seems to be the toughest to factor. And that case has had the most work on it because of the applications to cryptography so this isn’t due to drunks at the lampost.
On the other hand, in some respects factorization looks easier. Factorization (as phrased as the decision problem given earlier) lies in both NP and co-NP. In contrast, it is not known whether GI is in co-NP. Moreover, while factoring is in BQP, this has not been shown to be true for GI. (I’m not sure how much of big deal that is, and I really don’t know the quantum end well enough to evaluate how strong that is as evidence although my impression is that a lot of people have tried to show that GI is in BQP.) So in some senses, factorization fits more conditions which suggest being r actually in P.
Yeah, so this is a good point. The separation given by Grover’s algorithm is essentially a blackbox model. And Shore’s algorithm being better depends on the claim that factoring is not in P, which is a claim strictly stronger than P != NP (and a claim which is doubted by a lot more people. Henry Cohn for example says there’s no good reason to think that factoring is not in P.) So yes, this is under the black box. system.
Wait, so there’s significant support for the belief that RSA can be broken in polynomial time?
There’s significant support not for that per se but that there’s no good reason to think otherwise. I don’t know for example what estimate Henry Cohn would give for a polynomial time factoring algorithm but in conversations (and in at least one talk he gave) he’s pointed out that there’s no complexity theoretic reason to suspect that factoring is tough. Moreover, there’s a polynomial time factoring algorithm for Q[x] where Q is the rationals (if you don’t care about units). The argument for factoring being hard boils down solely to “lots of people have worked on this and haven’t succeeded.” But that’s a very weak argument especially when one looks at how much progress has been made in factoring in the last few years (see especially the number field sieve and elliptic curve sieve). This is in contrast to say the conjectures that P != NP and BPP = P where in order for them to be wrong various things need to happen that seem unlikely.
But normally, problems eventually found to be in P are first found to be in BPP (primality testing being the most prominent example). Shouldn’t there at least be some probabilistic factoring algorithms (whatever that would mean)?
Also, in the likely event that P != NP, that would imply the existence of NP-intermediate problems, and factoring is a good candidate for being in such a class.
(Personally, my hunch is that factoring is indeed in P, but I’m far from qualified to have a lot of confidence in that.)
This is an example where moving between a decision problem (returning a yes or no answer) and a function problem (returning a number or list of numbers) may break down. To make factoring equivalent to a decision problem one instead asks the question “Given n, and given a and b, is there are prime factor of n which is between a and b?” If one has a factorization of n one can answer this question quickly. If one has an oracle that can answer this question then one can factor in polynomial time by using a binary search tree of the intervals under n. This allows one to iterate calls to the oracle to find a prime factor in log_2 n time. Each time you find a prime factor p, you store it and then do the same process for n/p. This takes at most (log2 n) times the number of prime factors of n. In general, if calls to your oracle take time f(n), the whole thing takes at most f(n) (log2 n)^2 time. (You can actually do slightly better than that but this is good enough for pretty much all purposes.)
What I’m not sure about is whether the equivalent problem in BPP goes through. Say one has an oracle that answers the interval question with a BPP-like answer. Is there some way to turn that into a process that returns the correct factorization quickly with high probability? That’s not obvious to me. I haven’t really thought about the question that hard.
Right. That and and graph isomorphism seem to be the two most common natural problems that are potentially in that intermediate class.
I think you’d be in an extreme minority here. Even people like Henry who think that the evidence for factoring not being in P is small don’t seem to think it is actually in P. If I had to make a guess on the chance that factoring is in P, I’d probably put it at under 20%.
Yes, but I thought there’s much higher confidence that graph isomorphism will be de-randomized, given how hard it is to even find problem instances that are unresolved after a few simple checks (e.g. of invariants of the adjacency matrices).
Yes, graph isomorphism looks a lot more likely to drop straight into P.
Not only is it hard to find difficult problem instances, for almost any nice type of graph (e.g. planar graphs, or interval graphs) there’s a polynomial time algorithm. On the other hand, there about as many specific types of graphs where one can show that being able to solve graph isomorphism for that type of graph means you can solve it for all graphs. Connected graphs are a trivial example but regular graphs are a less trivial example. But the closest rough equivalents for factorization look tough. Primality testing is easy, and testing if n=p^k for some prime is about as easy. But in those cases if the answer is “no” then you can’t factor it easily! And almost any other natural set of integers has factoring be really tough. For example, consider Fermat and Mersenne numbers. In both cases, while factorization does seem to be easier it isn’t that much easier. One can object that these are defined in part in an additive fashion, but this doesn’t help since the most obvious multiplicative set of nice numbers, products of two primes, seems to be the toughest to factor. And that case has had the most work on it because of the applications to cryptography so this isn’t due to drunks at the lampost.
On the other hand, in some respects factorization looks easier. Factorization (as phrased as the decision problem given earlier) lies in both NP and co-NP. In contrast, it is not known whether GI is in co-NP. Moreover, while factoring is in BQP, this has not been shown to be true for GI. (I’m not sure how much of big deal that is, and I really don’t know the quantum end well enough to evaluate how strong that is as evidence although my impression is that a lot of people have tried to show that GI is in BQP.) So in some senses, factorization fits more conditions which suggest being r actually in P.