3 ms·
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_
by creata 6y ago
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_computer_science#Computational_complexity https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_c...
- adamnemecek 6y agoP == NP on analog quantum computers. A light prism performs a diagonalization which can be used to do factorization in O(1).
- rytill 6y agoFactorization of arbitrarily large numbers? I doubt it.
- adamnemecek 6y agoYes.
- amelius 6y agoOn constant-size hardware? And doesn't getting the data in and out already take O(N)?
- adamnemecek 6y agoAre you talking about arbitrary sized or infinite sized?
- rytill 6y agoWe’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).