Post

So just because I'm annoyed, here's the relevant part of the piece I was told to go read. Which I did. And I agree with everything in it. I've actually read this whole paper before. I think it's a good one.

Corey J. Maley

@coreymaley.net

It notes that Integer Factorization is NOT NP-hard. If it were, it would be intractable. I know that. But it *is* in sub-exponential, which is another class that is generally taken to be intractable. Also, Integer Factorization is in BQP: polynomial time for quantum computers. As it notes.

13/8/26, 9:23 pm0 reposts0 likes

Corey J. Maley

@coreymaley.net

13 Aug

Now this piece is right in saying that many people assume, incorrectly, that quantum computers can solve NP-hard problems. I know that too, and I never claimed it. Which is part of why I specifically mentioned that I get that Integer Factorization is in sub-exponential.

Corey J. Maley

@coreymaley.net

13 Aug

So I asked, isn't this a counterexample to the idea that hardware doesn't matter for intractability, assuming that sub-exponential is intractable? This line from the paper made me think that the original claim the person made was just not correct, by their own lights:

Corey J. Maley

@coreymaley.net

13 Aug

"The so-called Integer Factorization problem (Shor, 1997) provides an example: No polynomial-time algorithm is known (nor believed) to exist for Integer Factorization, yet the problem is efficiently computable by a quantum computer."

Corey J. Maley

@coreymaley.net

13 Aug

But because somewhere I said "NP" instead of "NP-hard", I was told to go do my homework because that's such a basic mistake it's too hard to explain. Because typos indicate ignorance.