Complexity for type-2 relations (Q922532): Difference between revisions

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.