Complexity for type-2 relations

DOI10.1305/ndjfl/1093635419zbMath0711.03017OpenAlexW2093400121MaRDI QIDQ922532

Mike Townsend

Publication date: 1990

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1305/ndjfl/1093635419

zbMATH Keywords

partial functionscomplexity classesstructural complexitytype-2 functionalstype-2 relation

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Higher-type and set recursion theory (03D65)

Related Items (10)

A tight relationship between generic oracles and type-2 complexity theory ⋮ Structural properties for feasibly computable classes of type two ⋮ Polynomial games and determinacy ⋮ Computation models and function algebras ⋮ Type 2 polynomial hierarchies ⋮ Complete and tractable machine-independent characterizations of second-order polytime ⋮ Type-two polynomial-time and restricted lookahead ⋮ Analytical properties of resource-bounded real functionals ⋮ The relative complexity of NP search problems ⋮ A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY

This page was built for publication: Complexity for type-2 relations