Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
1  
It is not necessarily the case that the best algorithm is to determinize the NDTM, but certainly this approach may be exponential in $m$. – András Salamon Jul 6 '13 at 17:36
    
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 $). – Abuzer Yakaryilmaz Jul 8 '13 at 8:22
up vote 9 down vote accepted

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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