A type-2 relation is a subset of \((\Sigma^*)^ n\times (^{\Sigma^*}\Sigma^*)^ n\), where \((Y)^ n=Y\times Y\times...\times Y\) (n times), and \((^ XY)=\{f:\) f is a partial function from X to \(Y\}\). The type-2 functionals are those partial functions whose domains are type-2 relations and the ranges are subsets of \(\Sigma^*\). The paper under review considers the extensions of many classes of ordinary structural complexity theory to the classes of type-2 functionals or relations. For example, the extensions of Poly (the class of polynomial time computable functions), P, NP, \(\Sigma^ p_ n\), \(\Pi^ p_ n\) (the classes of the polynomial hierarchy) are widely discussed. Furthermore, some topological concepts are introduced to type- 2 relations, and it is shown, by topological considerations, that the analogue of the \(NP=PSPACE\) question has a negative answer.
- The relative complexity of NP search problems
- A tight relationship between generic oracles and type-2 complexity theory
- Polynomial games and determinacy
- Analytical properties of resource-bounded real functionals
- Structural properties for feasibly computable classes of type two
- scientific article; zbMATH DE number 2163039 (Why is no real title available?)
- A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY
- Computation models and function algebras
- Type 2 polynomial hierarchies
- Complete and tractable machine-independent characterizations of second-order polytime
- A note on the relation between polynomial time functionals and Constable's class \(\mathcal K\)
- Second-order parameterizations for the complexity theory of integrable functions
- Complete and tractable machine-independent characterizations of second-order polytime
This page was built for publication: Complexity for type-2 relations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q922532)
