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.
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.