One thing particularly interesting about this is that Graph Isomorphism is in a hypothetical category of problems sometimes dubbed "NP-intermediate": they are b

One thing particularly interesting about this is that Graph Isomorphism is in a hypothetical category of problems sometimes dubbed "NP-intermediate": they are believed to be hard, but nobody has proven they're NP-complete. Linear programming used to be one of these, but was proven (rather brilliantly) to be in P by Leonid Khachiyan in 1979. Notably, as far as I know, it hasn't been proven that NP-intermediate even exists. It's quite possible that all problems believed to be in that category are actually either P or NP-complete. If this proof is on the right track, this possibility may be all the more likely.