Defining decision-problem complexity classes by counting branches of a polynomial-time NTM

Question

This answer on another SE community discusses the concept of a "counting complexity class". As far as I can tell, the author is using that term in a slightly nonstandard way: most sources (PS format) use that term to refer to complexity class like #P of counting problems that count the accepting branches of a polynomial-time nondeterministic Turing machine (NTM). The author of the linked answer seems to be using the term to mean a complexity class C for decision problems such that C can be defined in terms of this count. Am I understanding this correctly?

If so, then I believe that all of the following counting complexity classes (in the latter sense of the term) can be defined in the form "C is the set of decision problems for which there exists a polynomial-time NTM such that ...". Am I completing the sentences correctly for each counting complexity class?

1. P: if the answer is yes then every branch accepts, and if the answer is no then every branch rejects. (My answer below explains why this definition is equivalent to the usual one.)

2. RP: if the answer is yes then a fraction $p$ of the branches accept, where $p$ is a positive number that does not depend on the input size. If the answer is no then every branch rejects.

3. co-RP: if the answer is yes then every branch accepts. If the answer is no then a fraction $p$ of the branches reject, where $p$ is a positive number that does not depend on the input size.

4. BPP: if the answer is yes then a fraction p of the branches accept, where $p > 1/2$ does not depend on the input size. If the answer is no then a fraction q of the branches reject, where $q > 1/2$ does not depend on the input size.

5. NP: if the answer is yes then at least one branch accepts. If the answer is no then every branch rejects.

6. co-NP: if the answer is yes then every branch accepts. If the answer is no then at least one branch rejects.

7. C$ _=$P: if the answer is yes then exactly half the branches accept. If the answer is no then the fraction of accepting branches does not equal $1/2$.

8. PP: if the answer is yes then most branch accept, and if the answer is no then at least half the branches reject.

One advantage of this formulation is that it makes obvious the class inclusions P $\subset$ (co-)RP $\subset$ BPP (using this trick) $\subset$ PP and (co-)RP $\subset$ (co-)NP $\subset$ PP (using Buchfuhrer's trick here).

Note: In order to make this question clearer and more useful for future viewers, I have edited it to make every definition correct. The definitions in the original version of my question (available in the question history) had a few errors, which Ariel pointed out in their answer.

Answer 1

In the abstract of Counting classes: thresholds, parity, mods, and fewness”, by Beigel and Gill, any class of languages whose membership of some input $x$ can be determined by some function of $\#M(x)$ (the number of accepting paths of the NTM $M$ on input $x$) is considered a counting class.

In regards to your "counting description" of some known classes, your characterization of $\mathsf{ZPP}$ is actually a description of $\mathsf{P}$ (there is no mentioning of the power of expected polynomial time over worst case polynomial time). Additionally, your description of $\mathsf{P}$ is not very clear, a Turing machine can be either deterministic or non deterministic (those are different models of computation), so there is no NTM which is "actually deterministic". It is not clear how to give a counting characterization of $\mathsf{ZPP}$, since it differs from the rest of the classes by relaxing the polynomial time property.

Additionally, note that in the NP/coNP case you have an equivalence, i.e. $x\in L$ iff there exists some accepting path/ iff all paths are accepting. Requiring only one implication results in a stronger class.

Answer 2

Ariel explained to me in chat the way to see why the definition 1 above is equivalent to the usual definition of P, which is the set of problems solvable by a polynomial-time deterministic Turing machine.

The $\Leftarrow$ direction is trivial: just choose a formally nondeterministic Turing machine that never branches and is functionally identical to the deterministic Turing machine. (I tried to choose my words carefully ... Ariel feels strongly that such a machine is not in fact deterministic, but nondeterministic with a transition relation that happens to to be single-valued.)

The $\Rightarrow$ direction is also easy: since every branch of the NTM gets the right answer, just make it deterministic by arbitrarily choosing a single branch and choosing a DTM equivalent to that branch.