2:43 PM
@user777 Well, the page says that the problem is "designed to be hard", not that it actually is hard for some complexity class. If $f$ is used as an oracle, then the Deutsch–Jozsa problem cannot be solved in polynomial time by a deterministic classical computer, and therefore is not in P. However, we do not know whether it we can solve this problem faster classically if can use more information of $f$.
8
To my understanding, Deutsch-Jozsa algorithm solves a specific problem in constant time, using a fixed circuit depth, compared to a classical deterministic algorithm, which would require time exponential to the number of bits used to store the input. I thought this proves that there exist certai...
3:29 PM
but it is strange that there exists some problem that are not in P and computable, but we don't know: how hard is it?
I would like to know if you know any other problems with the same properties, so people cannot classify some problems because we don't know which class fits on.
« first day (2817 days earlier) ← previous day next day → last day (1623 days later) »