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.

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.

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.

Oh well. People have a right to believe that they cannot possibly be wrong, and if you question them, then you're obviously an ignorant jerk who is acting in bad faith and didn't read what they said they did. Because experts never make mistakes, or misread others' questions.

This exact story seems to play out weekly with that set of people, unfortunately.