2
$\begingroup$

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}$" ?

$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

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