Define is an LBA that accepts input w}. Show that is PSPACE-complete.

A problem is PSPACE-complete if uses memory polynomial in the input length. Also, the problem that is PSPACE-complete can be transformed to polynomial time.

$A_{LBA}$is PSPACE-complete

We will assume that

$L\in PSPACE$

$M$belongs to PSPACE and will occupy direct space. The machine$M$will be imitated on $w$.

Reducelocalid="1663229025556" $L$to$A_{LBA}$such that$L{\le }_p{A}_{LBA}$$L{\le }_p{A}_{LBA}$

• A decider $M$will campaign in the space $s^n$since $L\in PSPACE$. The end goal is such that $L\left(M\right)=L$.
• For the input $w$ the output will be .
• If $w{\left(\Gamma \right)}^{{\left|w\right|}^n}$is accepted by $M$then $w\in L$
• For the input $w{\left(\Gamma \right)}^{{\left|w\right|}^n}$the machine $M$ will go about as LBA because the machine $M$is campaigning in the space$s^n$

Now bring down QBF from a PSPACE-complete job into$A_{LBA}$

• Take a Turing machine where for any input w and a multinomial function f it will utilize at the most $f\left(\left|w\right|\right)$ cell and will settle QBF.
• Take a Turing machine and $\delta$will have the lowest superset $\delta \text{'}$.
• Every QBF equation is assigned into by a function g. Here B is the vacant character where the relation is true.
• This function g which is bringing down QBFfromPSPACE-complete job into role="math" localid="1663230085233" $A_{LBA}$is the poly-time reduction.

Thus, it is proved that $A_{LBA}$is PSPACE-complete.