Complexity for type-2 relations
type: Item
instance of: scholarly article
title: Complexity for type-2 relations
zbMATH Open document ID: 0711.03017
author: Mike Townsend
published in: Notre Dame Journal of Formal Logic
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D65
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 4168666
zbMATH Keywords: complexity classes
zbMATH Keywords: type-2 relation
zbMATH Keywords: type-2 functionals
zbMATH Keywords: partial functions
zbMATH Keywords: structural complexity
reviewed by: Xizhong Zheng
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1305/ndjfl/1093635419
OpenAlex ID: W2093400121
DOI: 10.1305/NDJFL/1093635419
description: scientific article; zbMATH DE number 4168666