complexity classes NP vs. BPP and similar

Question

I do not understand well the relation between nondeterministic class $\mathsf{NP}$ and a probabilistic one, say $\mathsf{BPP}$. Both uses some guesses and random decisions.What is the most direct observation that would allow me to understand the difference ? I do believe some obvious inclusions between such classes but not the essence of the difference. Also, what is the difference between halting in polynomial time with probability 1, and halting in it always.

Answer 1

NP doesn't use random decisions, and BPP doesn't use guesses.

Decision problem is in BPP if you can solve it fast using coin toss and being correct most of the time. Decision problem is in NP, if you can check solution if there is one.

I don't think this is a very good formulation, but if we try to define them in some similar terms: you are given problem and hint (certificate in case of NP, results of coin toss in case of BPP).

For NP, if there is a solution, then there is a correct hint, and if there is no solution, there is no correct hint. It's well possible that most hints are incorrect. You need to be able to check hints perfectly.

For BPP, you are allowed to do mistakes for some hints, but you are required to process most possible hints correctly.

Relation between these classes is unknown. It is known that if P=NP then P=BPP, but it's possible that, for example, $\text{P} \subsetneq \text{NP} \subsetneq \text{BPP}$, or $\text{P} \neq \text{NP} = \text{BPP}$, or $\text{BPP} \not\subset \text{NP}$ and $\text{NP} \not\subset \text{BPP}$. I think most popular belief is $\text{P} = \text{BPP} \subsetneq \text{NP}$, but nobody currently knows if its true.

I don't think it's possible to halt in polynomial time with probability $1$ but not always, because if you halt with probability $1$ in time $p(n)$, you read at most $2^{p(n)}$ random bits. And if there is at least one sequence $x$ of coin tosses on which you don't halt, then you don't halt in time $p(n)$ with probability at least $2^{-p(n)}$ (if sequence has the same first $p(n)$ results as $x$, then you don't halt on it in time $p(n)$).