First Steps Towards Linking Membrane Depth and the Polynomial Hierarchy

Abstract

In this paper we take the first steps in studying possible connections between non-elementary division with limited membrane depth and the levels of the Polynomial Hierarchy. We present a uniform family with a membrane structure of depth d + 1 that solves a problem complete for level d of the Polynomial Hierarchy.