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

I don't know. That seemed condescending to me. Assuming I don't know what I'm talking about because of a typo, and I guess because I was talking about intractability not in terms of something being NP-hard, I was ignorant?

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.