11
$\begingroup$

The computation of a nondeterministic Turing machine (NTM) is well known to be representable as a tree of configurations, rooted at the starting configuration. Any transition in the program is represented by a father-child link in this tree.

Similar trees can also be constructed for visualising the computations of probabilistic and quantum machines as well. (Note that it is better for some purposes not to view the related graph for quantum computations as a tree, since two nodes representing identical configurations at the same level of the tree can "cancel" each other out, due to quantum interference, but this doesn't have anything to do with the present question.)

Of course, deterministic computations are not like that; there is a single "branch" in the corresponding "tree" for any run of a deterministic machine.

In all the three cases mentioned above, what sometimes makes these computations "difficult" for deterministic computers is not really that there is branching going on, rather, it is a matter of how much branching is present in the tree. For instance, a polynomial-time nondeterministic Turing machine which is guaranteed to produce computation trees whose "widths" (i.e. number of nodes in the most crowded level) are also bounded above by a polynomial function of the input size can be simulated by a polynomial-time deterministic TM. (Note that this "polynomial width" condition is equivalent to restricting the NTM to make at most a logarithmically bounded number of nondeterministic guesses.) The same thing is true when we put similar width bounds on probabilistic and quantum computations.

I know that this issue has been examined in detail for nondeterministic computations. See, for example, the survey "Limited Nondeterminism" by Goldsmith, Levy, and Mundhenk. My question is, has this phenomenon of "limited branching" or "limited width" been studied in a common framework encompassing all of the nondeterministic, probabilistic, and quantum models? If so, what is the standard name for it? Any links to resources will be appreciated.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
12
$\begingroup$

Nondeterministic computations can also be viewed as verification of claims using short proofs. That is, the class NTIME(t) can also be viewed as the class of languages $L$ such that a claim of the form $x \in L$ can be verified in time $t(|x|)$ by reading a short proofs. In this model, "quantifying the braching" is analogous to studying how short the proofs can be. While I don't know of papers that studied this question, this could give you a direction of where to look for them. One paper that studied a related question in the context of interactive proofs is "On Interactive Proofs with Laconic prover", by Goldreich, Vadhan, and Wigderson: http://www.wisdom.weizmann.ac.il/~oded/p_laconic.html

Regarding probabilistic computation: The amount of "branching" used in the computation is exactly the number of random bits/coin tosses that the algorithm uses. Quantifying this number and minimizing it is studied extensively in the area of "Derandomization". You can read about it in Chapters 20 and 21 of the Arora-Barak book (http://www.cs.princeton.edu/theory/index.php/Compbook/Draft) or in Chapter 8 of Goldreich's book (http://www.wisdom.weizmann.ac.il/~oded/cc-book.html). It should also be mentioned that the common belief in this area is that $P=BPP$. If this is true, then the number of random bits a computation uses does not affect its power, as long as this number is polynomial.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you! So the phenomenon in question corresponds to "reading a proof symbol" in the first case, and "tossing a coin" in the second one. But what about the third case, i.e. quantum? I would really appreciate it if someone who understands these things explained what the important difference between a quantum transition whose amplitude has modulus 1 (i.e. a "nonbranching" transition), and a branching one is. Is implementing quantum branchings more difficult, costly, etc. than implementing quantum nonbranchings, for instance? $\endgroup$
    – Cem Say
    Commented Mar 23, 2012 at 20:09
  • $\begingroup$ I cannot say anything rigorous right now but I think in the quantum case is the ammount of entanglement in the state of configurations your machine is currently at. If there is no entanglement it would be just like a probabilistic machine. So instead of counting the branching degree, maybe counting the amount of entanglement makes more sense in this case, e.g., computing the rank of the state (what physicists call Schmidt number), or any other way of measuring entanglement. But, like I said, this is just a thought. $\endgroup$
    – Marcos Villagra
    Commented Mar 24, 2012 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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