# Probabilistic and quantum analog of $FP$ and $FNP$?

Is there any analog of the computational classes $FP$ and $FNP$ with probabilistic or quantum Turing machines? If so, what are the relation with other computational classes?

• A series of comments before the experts show up: One natural variant is the class of promise problems, prBPP. Goldreich's paper "In a world of P=BPP" also defines "BPP search problems", I believe. Also I see that FBQP is defined at the complexity zoo but only one reference. Finally, notice that at least if we don't require the machine's answer to be checkable, then a probabilistic machine can solve impossible-deterministic problems, i.e. "given $n$, produce a string of Kolmogorov complexity at least $n$" (with prob >= 2/3). – usul Feb 13 '15 at 17:22
• What's the motivation for considering the functional variants of these classes? – Huck Bennett Feb 13 '15 at 18:43
• Well, usually decision problems are simpler and capture the complexity properties that we want to study. Also, your question has an easy answer for decision problems: BPP and MA are the probabilistic analogs of P and NP respectively, while BQP and QMA are the quantum analogs of P and NP respectively. I don't see why you care about sticking an "F" in front of any of these classes. – Huck Bennett Feb 13 '15 at 23:02
• @Huck Bennett - I don't understand your criticism: computing functions is usual in everyday math, and indeed your laptop not only decides problems but does also compute functions. Considering only decision problems limits our view. On the other hand, if men had had considered only simplest things, we wouldn't have had computers and not even wheels. – neophyte Feb 14 '15 at 8:52
• @SashoNikolov: actually, I was trying to say that Huck's point (and your first comment) was not the point :-) Huck asked for a motivation to consider functions instead of problems. I gave one: reductions. You say that "there are various ways to reduce back and forth between search and decision", but none of that would make sense if we were not able to define complexity-bounded functions (reductions). That FP doesn't add anything to P in terms of separation/equality issues seems to me to be beside the point. Maybe FP is not interesting as a class but some of its inhabitants are! – Damiano Mazza Feb 15 '15 at 9:34