On: Big O Notation – Explained as easily as possible

[creata]

Wikipedia has a list of big-name unsolved problems in complexity theory. Most of these have very simple problem statements.

https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_c...

[adamnemecek → creata]

P == NP on analog quantum computers. A light prism performs a diagonalization which can be used to do factorization in O(1).

[rytill → adamnemecek]

Factorization of arbitrarily large numbers? I doubt it.

[adamnemecek → rytill]

Yes.

[amelius → adamnemecek]

On constant-size hardware?

And doesn't getting the data in and out already take O(N)?

[adamnemecek → amelius]

Are you talking about arbitrary sized or infinite sized?

[rytill → adamnemecek]

We’re saying the time, space, or some other metric of the solution scales with the size of the input number in a way that is not constant. The number could be any input (arbitrary).