2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/33005We study the efficient approximability of basic graph and logic problems in the literature when instances are specified hierarchically as in \cite{Le89} or are specified by 1-dimensional finite narrow periodic specifications as in \cite{Wa93}. We show that, for most of the problems $Π$ considered when specified using {\bf k-level-restricted} hierarchical specifications or $k$-narrow periodic specifications the following holds: \item Let $ρ$ be any performance guarantee of a polynomial time approximation algorithm for $Π$, when instances are specified using standard specifications. Then $\forall ε> 0$, $ Π$ has a polynomial time approximation algorithm with performance guarantee $(1 + ε) ρ$. \item $Π$ has a polynomial time approximation scheme when restricted to planar instances. \end{romannum} These are the first polynomial time approximation schemes for PSPACE-hard hierarchically or periodically specified problems. Since several of the problems considered are PSPACE-hard, our results provide the first examples of natural PSPACE-hard optimization problems that have polynomial time approximation schemes. This answers an open question in Condon et. al. \cite{CF+93}.5 Figures, 24 pagesComputational ComplexityData Structures and AlgorithmsF.1.3; F.2.2text