Distributive Minimization Comprehensions and the Polynomial Hierarchy

arXiv1703.09328MaRDI QIDQ6284859FDOQ6284859

Authors: Joaquín Díaz-Boïls 

Publication date: 27 March 2017

Abstract: A categorical point of view about minimization in subrecursive classes is presented by extending the concept of Symmetric Monoidal Comprehension to that of Distributive Minimization Comprehension. This is achieved by endowing the former with coproducts and a finality condition for coalgebras over the endofunctor sending X to $1oplusX$ to perform a safe minimization operator. By relying on the characterization given by Bellantoni, a tiered structure is presented from which one can obtain the levels of the Polytime Hierarchy as those classes of partial functions obtained after a certain number of minimizations.

This page was built for publication: Distributive Minimization Comprehensions and the Polynomial Hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284859)