6
$\begingroup$

In the usual definition of probabilistic poly-time machine it is said that the machine halts in polynomial time for all inputs.

Is the intention really to say that the machine halts for all inputs, or that if it halts it must be in polynomial time?

$\endgroup$

migrated from cstheory.stackexchange.com May 24 '12 at 18:36

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ It has to halt on all input in polynomial time. $\endgroup$ – sdcvvc May 24 '12 at 20:21
6
$\begingroup$

We say that a probabilistic Turing machine M runs in time T(n) if for any input x M halts in less than T(|x|) steps independently of the random choices it makes during the computation (worst case over all possible computation paths).

For example, the most general definition of Probabilistic Polynomial-time, namely PP, is:

A language L is in PP if and only if there exists a probabilistic Turing machine M, such that

  • M runs for polynomial time on all inputs
  • For all x in L, M outputs 1 with probability strictly greater than 1/2
  • For all x not in L, M outputs 1 with probability less than or equal to 1/2.

It always halts in polynomial time on all inputs.

Because the two probabilities can be made very close ($\frac{1}{2}+\frac{1}{2^n},\frac{1}{2}-\frac{1}{2^n}$), it would take potentially an exponential number of runs to distinguish accepting from rejecting with good confidence; so a more representative and efficient probabilistic class is BPP (Bounded-error Probabilistic Polynomial-time):

A language L is in BPP if and only if there exists a probabilistic Turing machine M, such that

  • M runs for polynomial time on all inputs
  • For all x in L, M outputs 1 with probability greater than or equal to 2/3
  • For all x not in L, M outputs 1 with probability less than or equal to 1/3.

Again, M always halts in polynomial time on all inputs.

See also the complexity class RP (Randomized Polynomial time).

We have: $RP \subseteq BPP \subseteq PP$

$\endgroup$
  • $\begingroup$ (1) What in the question suggests that it is about (unrealistic) complexity class PP? I do not think that PP is a typical example of probabilistic complexity class (BPP is), and talking about PP seems like just a distraction. (2) Las Vegas algorithms are usually defined in terms of expected running time, so your statement “In general …” is probably too general to be true. But even in that case, it is about all inputs, not “most” or “typical” inputs, unless we talk about average-case complexity. $\endgroup$ – Tsuyoshi Ito May 25 '12 at 12:58
  • 2
    $\begingroup$ @TsuyoshiIto: (1) I just picked the larger class, but obviously I agree with you that BPP is more representative. Do you think I should modify the answer? (2) I saw the definition of probabilistic time complexity right after the definition of probabilistic TMs in at least two books (one of them is the Arora&Barak book, not the public draft) and two lecture notes, but perhaps it is not enough to use "in general" :-(. What do you suggest? $\endgroup$ – Vor May 25 '12 at 16:09
  • 2
    $\begingroup$ As for (1), the very first sentence, “Perhaps you mean PP,” sounds quite strange because OP probably did not mean PP. Something along “Let’s look at the most general definition of ‘probabilistic polynomial-time,’ namely PP,” might be better. As for (2), I do not have a good suggestion because there are many things in the question which require clarification. That is basically why I have not posted an answer. :) $\endgroup$ – Tsuyoshi Ito May 25 '12 at 17:28

Your Answer

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