patternMinor
Is the leapfrog automata problem in P?
Viewed 0 times
problemleapfrogtheautomata
Problem
-
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.
-
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$.
-
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?)
-
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
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.
-
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$.
-
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?)
-
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
Solution
$\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:
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.
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 register
Code Snippets
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.
DECREMENTContext
StackExchange Computer Science Q#127268, answer score: 8
Revisions (0)
No revisions yet.