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

  • 1
    $\begingroup$ It is not necessarily the case that the best algorithm is to determinize the NDTM, but certainly this approach may be exponential in $m$. $\endgroup$ Jul 6 '13 at 17:36
  • $\begingroup$ The problem given in Theorem 1 is NCM(m,r). So, both $ m $ and $ r $ are fixed. When you design an algorithm for this problem, you can embed the values of $ m $ and $ r $ into the finite state set. Moreover, you can squeeze the work tape to $O(\log n)$ space by using more tape symbols (depending the value of $ m $). $\endgroup$ Jul 8 '13 at 8:22

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.


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.