4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – usul Feb 13 '15 at 17:22
  • 1
    $\begingroup$ What's the motivation for considering the functional variants of these classes? $\endgroup$ – Huck Bennett Feb 13 '15 at 18:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Huck Bennett Feb 13 '15 at 23:02
  • 1
    $\begingroup$ @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. $\endgroup$ – neophyte Feb 14 '15 at 8:52
  • 2
    $\begingroup$ @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! $\endgroup$ – Damiano Mazza Feb 15 '15 at 9:34
2
$\begingroup$

I hope the following partially answers your question. I've never seen this observation published anywhere (please correct me if I'm wrong).

First of all, FQMA - a quantum analog of FNP - was defined: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fqma

One of the compelling reasons to define the complexity class NP is that there is a decision to search reduction: polynomial access to an oracle that solves NP-Complete problems allows you to search for a solution of any problem in FNP in polynomial time.

A decision to search reduction is not known between QMA and FQMA . For example, access to an oracle for the Local Hamiltonian problem is not known to be sufficient to efficiently construct a ground state.

Another related (although, not directly related to your question) reduction which is known for many classical NP problems, but not for QMA problems is downward self reducibility: A language L is downward self reducible if there is a cook reduction from L to itself such that the queries are shorter than the original input. For example, given a Local Hamiltonian H with m terms, decide whether its minimal energy is below a or above b (where b-a>1/poly) by asking questions regarding Hamiltonians which have m-1 terms or less. Many decision to search reductions have this additional property.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.