Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters? I was reading this paper, about the complexity of decision problems for
reversal bounded counter machines.
I got to Theorem 1 on Page 6.
The theorem shows that there's a log-space NTM which can determine if a non deterministic reversal-bounded counter machine is empty or not.
(A log-space NTM can be converted into a polynomial time DTM).
The proof shows that, for input machine represented as a string of length $n$,
with $m$ counters, that $O(m\log n)$ space is required.
Here's where I get lost. The paper says that, since $m$ is fixed, we can consider
the machine to take $O(\log n)$ space.
Does this mean that the algorithm is only uses log-space if $m$ is fixed? Would the corresponding deterministic algorithm then be exponential in terms of $m$?
If the number of counters or the number of reversals (or both) is part of the
input, the problem becomes coNP-complete (unless there is exactly one counter):

The upper bound was shown by Hague and Lin, using a reduction to existential Presburger arithmetic:
Hague and Lin, "Model Checking Recursive Programs with Numeric Data Types", CAV 2011, http://dx.doi.org/10.1007/978-3-642-22110-1_60.


If the number of counters is part of the input and one has exactly one
reversal, it is not hard to reduce the knapsack problem: Given
binary representations of $x_1,\ldots,x_k,y$, each containing at most $n$
bits, one can easily construct a $(k+1)n$-counter automaton $A$ that can nondeterministically pick a subset $S\subseteq \{1,\ldots,k\}$ and
produce $\sum_{i\in S} x_i$ on the first counter and then subtracts
$y$ from the first counter. Then the language of $A$ is non-empty
if and only if there is a subset $S\subseteq \{1,\ldots,k\}$ with
$\sum_{i\in S} x_i=y$.
If the number of reversals is part of the input and one has exactly
two counters, coNP-hardness was already shown in
Gurari and Ibarra, "The complexity of decision problems for finite-turn multicounter machines", http://dx.doi.org/10.1016/0022-0000(81)90028-3 .
This seems to be the journal version of the paper linked in the question.
If the number of reversals is part of the input and one has exactly
one counter, however, then the problem is NL-complete. This is a well-known
result on one-counter automata.