« first day (2817 days earlier)      last day (1623 days later) » 

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
Q: Why doesn't Deutsch-Jozsa Algorithm show that P ≠ BQP?

3yakuyaTo 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
@Discretelizard Thank you
Your reference is good, too.
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.
I remember reading sipser's textbook, saying that people spent time to classify Non-isomorphism problem and at the end they invent what is called, "Interactive proof system" for this problem
I mean if they have difficulty to classify a problem, then they invent a class that takes this problem.
 

« first day (2817 days earlier)      last day (1623 days later) »