Is the leapfrog automata problem in P?

Question

1. My question is whether a specific decision problem—finding a computation path through a "leapfrog automaton"—is in P or not. It's straightforwardly in NP, and it resembles the hamiltonian path problem in some respects, but it also seems a little easier and I haven't been able to find a reduction.

2. Definition. A leapfrog automaton is a special kind of machine. A leapfrog automaton consists of a finite number of registers each of which contains a nonempty word from $\Sigma^*$. There is also a special start register containing the empty word. At any given point, exactly one of the registers is marked as active; initially, it is the special start register.

   Like a DFA or NFA, a leapfrog automaton can consume words, accepting or rejecting them. Given a word $w$, if the word is empty, the automaton accepts. Otherwise, the automaton consumes the next symbol $\alpha$ in the word: if there is a register other than the active register whose word contains $\alpha$, the automaton nondeterministically picks one such register and sets it to active. It also nondeterministically picks one instance of the symbol $\alpha$ in the register and marks it as "visited". On the other hand, if none of the other registers have $\alpha$ in their word, the automaton rejects the word $w$.

3. Path problems. If a leapfrog automaton $M$ accepts a word $w$, we can examine all of the symbols that were marked as visited in all the registers during the computation. Suppose the machine maintains a record of which symbols in which registers were visited, in which order; this is called a computation path.

   The Blackout Decision Problem is: "Given a leapfrog automaton $M$ and a word $w$, is there an accepting computation path for $w$ which visits every symbol in every register at least once?" (Alternatively: exactly once?)

4. This Blackout Decision Problem is straightfowardly in NP; we nondeterministically choose a computation path and accept if it visits each symbol in each register exactly once, which is checkable in P.

   On the other hand, I'm not sure whether the problem is in P or not. I've been trying to construct a reduction from, say, HAMPATH, which would establish that the problem is NP-complete and would therefore convince me it isn't in P.

   Such a reduction might look like: Given a graph, construct a leapfrog automaton with one register for every node in the graph. The word in each register lists the nodes that are neighbors of that node. (Not sure where to go from here.)

So, to reiterate, is the blackout decision problem in P? Alternatively, can we show that it's NP complete?

---

Examples: A leapfrog automaton has two nonempty registers, containing VNS and ED, respectively. Among other words, it accepts VEND, EVEN, SEVEN, and the empty word. (Note how the order of letters in a register is irrelevant, and letters may be reused, and the first letter may come from any register.) It rejects the word SEVER, because the symbol R doesn't appear in any register. It rejects the words DEN and SEEN, because each letter must come from a different register than the one before.

Because the registers of this particular automaton have no letters in common, every computation path is unique and unambiguous[*]. In contrast, suppose we have a new automaton with three nonempty registers: HP AX A. The word HAX has exactly one accepting computation path, since each letter must come from a new register. The word HAPAX, however, has two accepting computation paths. One of those computation paths visits the third register "A" twice. The other path visits both letter "A"s. That other path is an example of a path that visits every symbol in every register at least once.

Because such a computational path exists, the Blackout Decision procedure, for this machine and this word HAPAX, answers yes (i.e. there is an accepting computational path for this word which visits every letter in every register at least once.)

---

ETA: If the alphabet is unary ($\Sigma = \{\mathtt{a}\}$) then the blackout problem is in P. The problem becomes finding a tour that visits each register the appropriate number of times while obeying the "different registers" constraint. Starting from the initial (empty) register, my algorithm is to iteratively visit whichever other register currently has the most unvisited letters (break ties arbitrarily). If there is a tour that satisfies the different-registers constraint, this procedure will find it.

Such a tour does not always exist when there are big disparities between the register sizes. For example, if the automaton has two nonempty registers AAAAAA and AAA, there is no accepting path (for any word!) that visits each letter in each register exactly once.

I haven't figured out whether the problem is efficiently solvable when the alphabet has two letters in it {A,B}.

---

[*] This implies that the Blackout Decision Problem for leapfrog automata is in P when we restrict to machines whose registers have no letters in common. The general case has branching factors which may make it harder than P.

Answer 1

$\newcommand{\nameq}{\stackrel{\tiny def}{=}}$

Problems

For an NP-completeness proof, let's rephrase the Blackout Decision Problem as "Given a leapfrog automaton $M$ and word $w$, does $M$ accept $w$ without revisiting any of its registers' symbols?". It's probably your intuition that the "visits each symbol once" version is no easier, and a reduction to that version is pretty easy, so I'll omit that.

We'll reduce to a problem I'll call DECAY-3SAT, which is a version of 3-SAT that allows the truth of each variable to decay to false in subsequent clauses. For example, $v_0=1$ (true) and $v_1=0$ (false) satisfies $(v_0\lor v_1 \lor v_1)\land(\lnot v_0 \lor v_1 \lor v_1)$ because $v_0$ can become false for the second clause. Note that the verifier still runs in polynomial time because it will be given the decay events along with the initial literal truth values. Additionally, DECAY-3SAT is no weaker than 3-SAT because a standard 3CNF formula $\phi$ with $n$ variables is satisfiable if and only if $\phi'\nameq\underbrace{\phi\land\dots\land\phi}_{n+1\text{ times}}$ is satisfiable with decay since one of those $\phi$ will be evaluated without decay, as decay can happen at most $n$ times (once per variable).

Reduction

Given a 3CNF formula $\phi\nameq C_0\land\dots\land C_{m-1}$, we will construct a leapfrog automaton $M$ with input $w$ such that $M$ accepts $w$ if and only if $\phi$ is satisfiable with decay.

Programming 3-SAT with Decay

For each clause $C_i$, make a symbol $c_i$ and put $2$ copies at register $2i$ and put $3$ copies at register $2i+1$. The idea here is to take away symbol $c_i$ each time a variable appears in clause $C_i$. If its current truth assignment satisfies $C_i$, we'll take $c_i$ away from the odd register, otherwise we'll take $c_i$ away from the even one. This forces at least one truth assignment to satisfy $C_i$.

Without yet going into the details, we can construct $M$ and $w$ in a way that implements simple programs made of 4 kinds of instructions. Those instructions and their use in this reduction are:

• $\texttt{NEW_VARIABLE_FIRST_CLAUSE}$: Go to register $0$ or $1$ nondeterministically.
  • Consider $v_j$ (0-indexed) as the current variable, where $j+1$ is the number of times $\texttt{NEW_VARIABLE_FIRST_CLAUSE}$ has been called. This should be the first instruction in any program.
  • This instruction chooses the initial truth value of $v_j$ (even means false, odd means true).
• $\texttt{NEXT_CLAUSE_DECAY}$: From the current register $r$, go to register $r+2$ or $r+2-(r\mod 2)$ nondeterministically. The second option may happen when $r$ is currently odd, which represents the variable decaying to false.
  • Call this $m-1$ times for each variable, or at least enough times to reach each clause $C_{\lfloor\frac{r}{2}\rfloor}$ that the current variable appears in.
• $\texttt{DECREMENT}$: Decrement count of the current clause symbol $c_{\lfloor\frac{r}{2}\rfloor}$ at current register $r$.
  • Call this as many times as the current variable appears as a positive literal in the current clause.
  • Note that when the current variable is true (i.e., $r$ is odd), this decrements from the odd register, and the clause is effectively satisfied.
• $\texttt{DECREMENT_NEGATED}$: Decrement count of current clause symbol $c_{\lfloor\frac{r}{2}\rfloor}$ at register $r+1-(r \mod 2)$.
  • Call this as many times as the current variable appears as a negative literal in the current clause.
  • Note that when the current variable is false (i.e., $r$ is even), this decrements from the odd register, and the clause is effectively satisfied.

Such a program will reject if it tries to decrement the number of clause symbols in a register that does not have any. Otherwise, it will accept. Hopefully that's enough to convince you that the NP-hardness reduction holds if we can actually construct an $M$ and $w$ to implement the program.

Implementing the 4 Instructions

Now comes the task of writing a compiler. We'll do so by adding symbols to $M$ and $w$ for successive instructions. Luckily the instructions are pretty restrictive, so we can track the current clause $C_i$ associated with each one, even though we don't know whether the current register will be $r=2i$ or $r=2i+1$ during execution.

To guide execution through the appropriate registers, most symbols we introduce will have the clause index $i$ as a subscript. For example, we'll add quite a few $\lambda_i$ symbols to registers $2i$ and $2i+1$ simply as a way to jump between them.

• Initially: For each clause $C_i$, put $3$ copies of its symbol $c_i$ in register $2i+1$ and put $2$ copies in register $2i$.
  • Mentioned in the previous section; copied here for completeness.
• $\texttt{NEW_VARIABLE_FIRST_CLAUSE}$: Add $\lambda_0$ to registers $0$ and $1$ in $M$. Append $\lambda_0$ to $w$.
  • When $M$ encounters $\lambda_0$ it will go to register $0$ or $1$ and consume the symbol. Pretty straightforward.
• $\texttt{DECREMENT}$: Add $\lambda_i$ to registers $2i$ and $2i+1$. Append $\lambda_i c_i$ to $w$.
  • The automaton, currently at register $2i$ or $2i+1$, will jump to the other of those two registers to consume $\lambda_i$, then it will jump back to its first register to consume the $c_i$ symbol.
• $\texttt{DECREMENT_NEGATED}$: Add $\lambda_i$ to registers $2i$ and $2i+1$. Append $c_i \lambda_i$ to $w$.
  • The automaton, currently at register $2i$ or $2i+1$, will jump to the other of those two registers to consume $c_i$, then it will jump back to its first register to consume the $\lambda_i$ symbol.
• $\texttt{NEXT_CLAUSE_DECAY}$: Add $\delta_i$ to registers $2i$ and $2i+3$. Add $\lambda_{i+1}$ to registers $2i+2$ and $2i+3$. Append $\delta_i \lambda_{i+1}$ to $w$.
  • If the current register is $2i$, this step is straightforward. First the automaton jumps to register $2i+3$ to consume the $\delta_i$ at register $2i$. Then it jumps to register $2i+2$ to consume $\lambda_{i+1}$. In this way, a false variable progresses to the next clause without losing its falseness.
  • If the current register is $2i+1$, there are a few paths to take.
    • Case 1: First, the automaton jumps to register $2i$ to consume $\delta_i$, then it jumps to register $2i+3$ to consume $\lambda_{i+1}$. In this way, a true variable can progress to the next clause while retaining its truthiness.
    • Case 2: The automaton jumps to $2i$ to consume $\delta_i$ then jumps to $2i+2$ to consume $\lambda_{i+1}$. The variable's truthiness has decayed.
    • Case 3: The automaton jumps to $2i+3$ to consume $\delta_i$ then jumps to $2i+2$ to consume $\lambda_{i+1}$. The variable's truthiness has decayed.

Example

For clarity, here's a construction for $\phi = (v_0\lor v_1 \lor v_1)\land(\lnot v_0 \lor v_1 \lor v_1)$. We'd write a program:

NEW_VARIABLE_FIRST_CLAUSE  // Choose v[0].
DECREMENT  // v[0] appears in the first clause.
NEXT_CLAUSE_DECAY
DECREMENT_NEGATED  // v[0] appears as negated in second clause.
NEW_VARIABLE_FIRST_CLAUSE  // Choose v[1]
DECREMENT  // v[1] appears twice in the first clause.
DECREMENT
NEXT_CLAUSE_DECAY
DECREMENT  // v[1] appears twice in the second clause.
DECREMENT

This complies to a leapfrog automaton $M$ with 4 registers, 2 for each clause, and a word $w$.

• $w=\lambda_0 \lambda_0 c_0 \delta_0 \lambda_1 c_1 \lambda_1 \lambda_0 \lambda_0 c_0 \lambda_0 c_0 \delta_0 \lambda_1 \lambda_1 c_1 \lambda_1 c_1$.
• Register $0$: $2 c_0$, $5 \lambda_0$, $1 \delta_0$.
• Register $1$: $3 c_0$, $5 \lambda_0$.
• Register $2$: $2 c_1$, $5 \lambda_1$.
• Register $3$: $3 c_1$, $5 \lambda_1$, $1 \delta_1$.

Answer 2

Just want to augment grencez's excellent answer with some gadget illustrations:

1. There are two registers corresponding to each clause, plus two variable-initialization registers.

   

2. Each clause has three unique symbols/colors, $C_i$ $v_i$, $\delta_i$. Those colors only appear in the clause's two registers, helping to constrain movement.

3. Each pair of registers is initialized with five $C_i$ symbols arranged as follows:

   

   This gadget helps enforce the rule that the clause must be satisfied by at least one literal.

4. To translate a formula $\Phi$ into a leapfrog automaton and agenda, we read the formula $\Phi$ and iterate over the variables in turn.

   a. First we add a variable initialization gadget

   b. Then we iterate over each clause, checking whether the variable occurs. For each clause, we add a goto-next-clause gadget:

   

   c. For every time the variable appears as a positive literal in the clause, we add a positive literal gadget. For every time the variable appears as a negative literal in the clause, we add a negative literal gadget. (They are identical except for the agenda order.)

   

   

5. By tightly controlling the available transitions, this process creates a leapfrog automata that is winnable if and only if the original formula is DECAY-3SAT satisfiable:

[Interaction 1] When a variable assignment (whether true or false) satisfies the clause, a $c_n$ symbol is removed from the top register. Otherwise, it is removed from the bottom register. Because there are three literals in the clause, the game is unwinnable unless at least one is removed from the top.

[Interaction 2] Because there are two registers per clause, the current register simultaneously encodes (a) what clause we're currently considering and (b) whether the current variable has been assigned true or false. Because these are DECAY-3SAT problems, the goto-next-clause gadget allows a true assignment to optionally decay into a false assignment at any point, while preventing the reverse decay.