A ladderis a sequence of strings s1, s2, . . . ,sk, wherein every string differs from the preceding one by exactly one character. For example, the following is a ladder of English words, starting with “head” and ending with “free”:head, hear, near, fear, bear, beer, deer, deed, feed, feet, fret, free.

Let

$\begin{array}{l}\mathbf{L}\mathbf{A}\mathbf{D}\mathbf{D}\mathbf{E}{\mathbf{R}}_{\mathbf{D}\mathbf{F}\mathbf{A}}\mathbf{=}\mathbf{\left\{}\mathbf{\right(}\mathbf{M}\mathbf{,}\mathbf{s}\mathbf{,}\mathbf{t}\mathbf{\left)}\mathbf{\right|}\mathbf{M}\mathbf{i}\mathbf{s}\mathbf{a}\mathbf{D}\mathbf{F}\mathbf{A}\mathbf{a}\mathbf{n}\mathbf{d}\mathbf{L}\mathbf{\left(}\mathbf{M}\mathbf{\right)}\mathbf{\text{\hspace{0.05em}containsaladderofstrings,}}\\ \mathbf{\text{startingwithsandendingwitht}}}\end{array}$

Show that $\mathit{L}\mathit{A}\mathit{D}\mathit{D}\mathit{E}{\mathit{R}}_{\mathbf{D}\mathbf{F}\mathbf{A}}$ is in PSPACE.

PSPACE is the collection of all decision problems that a Turing machine can answer using a polynomial space in computational complexity theory

The machine always comes to a halt by storing a counter that advances with each estimate and rejects when the counter reaches $|\sum {|}^{\left|s\right|}$. There is a length of at most$|\sum {|}^{\left|s\right|}$due to the presence of a chain from s to t.

If $\left|s\right|\ne \left|t\right|$for $(M,s,t)$ is true, reject it. Otherwise, assume a graph G of exponential size where the vertices are indexed by string in $|\sum {|}^{\left|s\right|}$and a directed edge exists between $w_1$and $w_2$, if it differs by exactly one character and $(w_1,w_2)\in L\left(M\right)$.

Hence $(M,s,t)$is a member of LADDER. if there is a path in G from s to t, a path can be predicted from there and verified that M accepts $w_2$by selecting a nondeterministic newvertx that differs from ${\mathit{w}}_{\mathbf{1}}$ by exactly one character.