We consider a slightly extended version of a nondeterministic finite automaton, call it a "propositional nondeterministic finite automaton". It is defined as follows. Consider a fixed propositional language $L_A$ built over a finite set of propositional variables $A$. $L_A$ is together with the usual logical connectives $\wedge$, $\vee$, $\neg$, etc. A propositional nondeterministic finite automaton is a tuple $(Q, \Sigma, \Delta, q_*, prop)$, where $Q$ is a finite set of states, $\Sigma$ is a finite set of symbols, $\Delta \subseteq Q \times \Sigma \times Q$ is a transition relation, $q_* \in Q$ is called the initial state, and $prop$ is a mapping from $Q$ to $L_A$.

Given a state $q \in Q$ and a symbol $a \in \Sigma$, we say that $(q, a)$ is an "admissible transition" if there exists a state $q' \in Q$ such that $(q, a, q') \in \Delta$.

Recall that a (propositional) interpretation (on $A$) is a mapping from $A$ to $\{0, 1\}$, and a model of a propositional formula is an interpretation that satisfies the formula in the usual way.

We consider the following decision problem. Given a propositional nondeterministic finite automaton $(Q, \Sigma, \Delta, q_*, prop)$, a property $P$ on any finite serie of propositional interpretations $(I_1, \dots, I_n), n > 0$ that can be checked in polynomial time (i.e., in $O(n^i)$ steps, where i is some constant), and a non-negative integer $k$ given in binary notation, determine whether there exists a model $I_0$ of $prop(q_0)$ where $q_0 = q_*$, and a symbol $a_1 \in \Sigma$ where $(q_0, a_1)$ is an admissible transition, such that for every state $q_1 \in Q$ where $(q_0, a_1, q_1) \in \Delta$, there exists a model $I_1$ of $prop(q_1)$ and a symbol $a_2 \in \Sigma$ where $(q_1, a_2)$ is an admissible transition, such that for every state $q_2 \in Q$ where $(q_1, a_2, q_2) \in \Delta$, there exists \dots, there exists a model $I_k$ of $prop(q_k)$ such that the serie $(I_0, \dots, I_k)$ of propositional interpretations satisfies the property $P$.

I would like to characterize the complexity of this problem (belongness and hardness). Actually, I am interested in a specific property $P$ which is parametrized by a non-negative integer $s$, i.e., the property $P_s$ defined as follows: a serie of propositional interpretations $(I_1, \dots, I_n), n > 0$, satisfies $P_s$ if for each $i \in \{1, \dots, n-1\}$, the Hamming distance between $I_i$ and $I_{i+1}$ is below $s$. However, the "hardness" part may be easier to prove if one considers the generic form of the decision problem with any property $P$ checked in polynomial time.

For the "belongness" part: this decision problem looks like the canonical $\mathsf{PSPACE}$-complete problem $True-QBF$: indeed, there is an alternation of existential and universal quantifiers. But the main problem is that since $k$ is given in binary form, the length of this sequence of these alternative existential/universal quantifiers is exponential ($= 2^{|k|}$), as well as the size of the serie $(I_0, \dots, I_k)$. Is $\mathsf{EXPTIME}$ the class to which this problem belong to? In any case, I would be happy to get the intuition of the proof for the non-expert I am.


1 Answer 1


$\DeclareMathOperator\prop{prop}$Allowing general poly-time properties $P$ unnecessarily blows up the complexity, it makes the problem complete for EXPSPACE = AEXPTIME. On the one hand, the definition of the problem itself is more or less a description of an exponential-time alternating Turing machine that solves it. On the other hand, let $L$ be an AEXPTIME problem. By standard elementary manipulations, $L$ can be solved by an alternating TM which is given the length $n$ of its input on a tape, and its computation proceeds by first making $2^{n^c}$ alternating universal and existential choices of bits that are recorded on an auxiliary tape, followed by a deterministic computation. In other words, $$\tag{$*$}w\in L\iff\forall a_1\,\exists b_1\,\forall a_2\,\cdots\,\exists b_{2^{|w|^c}}\,P(w,a_1,b_1,\dots,a_{2^{|w|^c}},b_{2^{|w|^c}}),$$ where $a_i,b_i\in\{0,1\}$, and $P$ is a polynomial-time predicate (note that this gives it exponential time in terms of $|w|$, because the length of $P$’s input is $O(2^{|w|^c})$). This can be reduced to your problem as follows. Let $A=\{u,v\}$, and $|\Sigma|=1$ (so I will just ignore symbols in the description). Given a word $w$ of length $n$, we construct an automaton with states $\{q_0,\dots,q_{n-1},r_0,r_1\}$. There are transitions from $q_i$ to $q_{i+1}$, and the formula $\prop(q_i)$ is $\neg u\land\neg v$ or $\neg u\land v$ depending on $w_i$; note that this forces $I_0,\dots,I_{n-1}$ deterministically to essentially equal $w$ (mixed with irrelevant $0$’s). Then we have transitions from each of $q_{n-1},r_0,r_1$ to each of $r_0,r_1$, and $\prop(r_0)=\neg u$, $\prop(r_1)=u$. The point is that when we are in $r_i$, the quantifiers “for each state $r_j$ with $(r_i,r_j)\in\Delta$ there exists $I\models\prop(r_j)$ such that ...” resolve to “for every $u\in\{0,1\}$ there is a $v\in\{0,1\}$”, with $I_j=(u,v)$. Thus, if we run the whole thing for $k=n+2^{n^c}$ steps, the sequence of the $I$’s will consist of a copy of $w$ plus a sequence $a_1,b_1,\dots,a_{2^{n^2}},b_{2^{n^2}}$ that were quantified the same way as in $(*)$.

In contrast, your specific $P_s$ can be handled much more efficiently, because it only restricts possible transitions from one step to the next one. You can incorporate $I$ into the state of the automaton, and since you are not discussing acceptance of any words, you can get rid of the alphabet as well. That is, your problem is easily reducible to the alternating reachability problem, and as such it is solvable in P (deterministic polynomial time).

Rather than the reduction, let me give the final algorithm. Let us define that $(q_0,a_0,I_0)\in Q\times\Sigma\times\{0,1\}^A$ is $n$-step admissible if for every $q_1$ such that $(q_0,a_0,q_1)\in\Delta$, there exists $I_1\models\prop(q_1)$ with Hamming distance $\delta(I_0,I_1)\le s$ and an admissible transition $(q_1,a_2)$ such that etc up to $q_n$. Note that $A$ is fixed, hence $2^{|A|}$ is constant, hence the set $X$ of all possible triples has polynomial size $O(|Q||\Sigma|)$. We can thus compute the set $X_n$ of $n$-step admissible triples inductively by putting $X_0=X$, and then given $X_n$, check all the polynomially many possibilities to determine $X_{n+1}$. Since $X_0\supseteq X_1\supseteq X_2\supseteq\dots$, the sequence will stabilize after $m\le|X|$ steps, at which point we know the answer to the original question for $k$ (even if it is given in binary).

It is also not hard to establish that the problem is in fact P-complete.

This answers the question as stated. Your comments below indicate that you somehow do not like the fact that $2^{|A|}$ is constant, but then you need to clarify the question, since I have no idea would else could “consider a fixed propositional language $L_A$ built over a finite set of propositional variables $A$” possibly mean.

If I just ignore this sentence completely and allow formulas over an arbitrary $A$ which is given as a part of the input, then the problem becomes complete for EXP = APSPACE. On the one hand, the alternating exponential time solution from the beginning becomes alternating polynomial space, as we do not have to keep more than two assignments at a time in memory. One can show EXP-hardness by simulating alternating polynomial-space machines. As a rough sketch, the states $Q$ of the automaton will encode the state of the simulated machine, the position of tape head, and the symbol below the head, while propositional assignments $I$ will simulate the content of the tape. One can arrange that a Hamming distance $1$ constraint will ensure the coherence of the tape from one step to another. Additional propositional variable or two can be used to simulate existential choices of the machine, while universal choices can directly correspond to nondeterminism of the automaton.

Concerning your comment (2): as long as the properties can be checked on the fly while keeping only a polynomial-size data, the problem will still be solvable in EXP, but there is no telling whether it can be done more efficiently without knowing the properties.

  • $\begingroup$ The problem for general poly-time properties is EXPSPACE-complete, and it’s not particularly difficult to prove it. I can supply more details for either of the two claims, but not now, it’s almost midnight. $\endgroup$ May 18, 2014 at 21:51
  • $\begingroup$ Thank you very much for your help. May I ask questions about your answer? 1) I do not understand the comment "Since A is fixed, you can incorporate I into the state of the automaton". What do you mean by "incorporate"? Since the set of interpretations (let us denote it $\Omega$) is of size $2^{|A|}$, I do not want to change the definition of the set of states of an automaton from a set $Q$ to a cartesian product $Q \times \Omega$. I think I just misunderstood your point. $\endgroup$
    – user109711
    May 19, 2014 at 6:03
  • $\begingroup$ 2) Actually, I have a few properties (in addition to $P_s$) on a chain $(I_0, \dots)$ of interpretations that are to be checked (4 in total, and my ultimate goal is to draw a complexity map of the decision problem when any subset of these 4 properties is considered). They are parametrized by a non-negative integer. To check them, we need to store a number when browsing the chain; however, such numbers may take the same amount of space to be represented, as the input parameters. Wouldn't it increase the complexity by considering such additional properties? $\endgroup$
    – user109711
    May 19, 2014 at 6:07
  • $\begingroup$ 3) I cannot find any reference on the web for the "alternative reachability game problem" or "alternating reachability game problem". I found something about graphs and winning/loosing nodes for some specific player, but I do not see the link with my problem, since in my case every interpretation of the serie will play a role in the satisfaction of the property. You also said ", which is solvable in polynomial time". Do you mean, on an alternating Turing machine? Then, do you mean the problem is in $\mathsf{AP} = \mathsf{PSPACE}$? $\endgroup$
    – user109711
    May 19, 2014 at 6:07
  • $\begingroup$ 4) Do you have a canonical problem in mind for the hardness of the problem? $\endgroup$
    – user109711
    May 19, 2014 at 6:09

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.