# Complexity lower bound for problem in $2^k \cdot 2^{|A|}$ with monotonicity in $k$

My decision problem deals with synthesis from register automata:

• input: a register automaton $$A$$, a number $$k$$;
• return YES if there exists $$k$$-register transducer that realizes the automaton, else NO.

(The meaning of terms 'synthesis', 'register automata', 'transducer', 'realizes' is not important.)

The problem upper complexity bound is $$O(2^{k}\cdot 2^{|A|})$$. Q1: What complexity class is this? Something from "parameterized complexity"? (which I am not familiar with)

Now to the second question. My problem has the monotonicity property: if the answer is YES for given $$A$$ and $$k$$, then the answer is YES for every larger $$k$$. This makes me believe that the problem is easier than EXP-hard in $$k$$. The not-quite working argument is the following (Q2: have you seen something similar?). Fix an arbitrary language L in APSPACE-hard (and recall that APSPACE=EXPTIME). For the sake of contradiction, suppose there exists a poly-time reduction to our problem that produces exactly-same$$^?$$ $$A$$, but varies $$k$$. With this reduction, we create an algorithm that decides L in polynomial time, for almost-all$$^?$$ words in L (contradicting to $$L$$ being EXPTIME-hard). The idea is to run the reduction, but before running our-problem-solver on the produced instance, check if the result follows from applying the monotonicity to the current value of $$k$$ and its previously computed values $$k_{no}$$ and $$k_{yes}$$:

• $$k_{no}$$ is the largest $$k$$ that we computed so far such that our-problem-solver returned (hence if $$k\leq k_{no}$$ we can immediately return NO, based on the monotonicity);

• $$k_{yes}$$ is the smallest $$k$$ that we computed so far such that our-problem-solver returned YES (hence if $$k\geq k_{yes}$$, return YES);

The above argument does not quite work, because (1) it assumes that the produced automaton $$A$$ is exactly the same for every word in the language $$L$$ (while by reduction definition, those $$A$$s shall only have the same size), and (2) not all words in $$L$$ are decided in polynomial time: a finite number of words requires exponential time. Q2: Have you seen something similar? ("monotonicity"? "almost-all poly-time reduction"? "exactly-same rather than same-size parameter in the reduction"?)

• hm, interesting why downvote. – Ayrat Feb 10 at 16:40