Presentation
First Steps Towards Linking Membrane Depth and the Polynomial Hierarchy
Author/s | Porreca, Antonio E.
Murphy, Niall |
Publication Date | 2010 |
Deposit Date | 2016-03-30 |
Published in |
|
ISBN/ISSN | 9788461423576 |
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 ... 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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
20polyheir.pdf | 216.8Kb | [PDF] | View/ | |