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"?)

  • $\begingroup$ hm, interesting why downvote. $\endgroup$ – Ayrat Feb 10 at 16:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.