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.

13/8/26, 9:23 pm0 reposts1 like

Corey J. Maley

@coreymaley.net

13 Aug

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.

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