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.

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.

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:

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

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.