# Counting certificates for a language

Let $M_{1}$ and $M_{2}$ be two (non-deterministic) turing machines accepting the language $L \subseteq \Sigma^{\ast}$.

Is is right to claim that:

$\#M_{1} \in \textbf{#C}$ if and only if $\#M_{2} \in \textbf{#C}$ ?

where $\textbf{#C}$ is a counting complexity class, that is closed under reductions (such as $\textbf{#P}$, $\textbf{#P-Hard}$, $\textbf{GapP}$, $\textbf{GapP-Hard}$, $\textbf{PP}$, etc).

If so, can we use the notation "$\#L \in \textbf{#C}$" ?

Take the language to be $L=\Sigma^*$. $L$ can be solved trivially, so there is a polytime NTM that doesn't use any nondeterminism and solves $L$, call it $M$. The counting function for $M$ is $\#M(x)=1$ which is trivial.

Take $N$ be the following polytime NTM:

$N :=$ on input $x$,
1. nondeterministicly guess $b\in\{0,1\}$,
2. nondeterministicly guess an assignment $\tau$ for $x$,
3. if $b=0$,accept,
4. if $b=1$ and $\tau$ satisfies $x$, accept.
5. otherwise reject.

It is easy to see that $L(N) = L = L(M)$. However $\#N(x)=2^{numvar(x)}+\#SAT(x)$ which is essentially $\#SAT$ and is complete for $\#P$.

$numvar(x)$ denotes the number of propositional variables in $x$.

Therefore the notation $\#L$ is not well-defined (even if we assume $L \in \mathsf{NP}$). You have to fix a NTM $M$ first for $L$ and then talk about $\#M$. Depending on the NTMs you choose for $L$ you will get different counting languages.

In some cases like $SAT$, the intended NTM for the language is clear from context. In such cases, we may use the notation $\#L$ to mean $\#M$ where $M$ is the intended NTM for $L$. Note that even in those cases we are still fixing an NTM for $L$, we just don't state that explicitly.