Structural properties for feasibly computable classes of type two

DOI10.1007/BF01374524zbMath0751.68024MaRDI QIDQ4009811

Tomoyuki Yamakami

Publication date: 27 September 1992

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

reductionseparationpolynomial hierarchystructural complexityextension propertypre-wellordering

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

A tight relationship between generic oracles and type-2 complexity theory ⋮ Polynomial games and determinacy ⋮ Helping by unambiguous computation and probabilistic computation ⋮ Resource bounded immunity and simplicity ⋮ A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• Complexity for type-2 relations
• Complexity classes without machines: on complete languages for UP
• Polynomial and abstract subrecursive classes
• Feasible computability and resource bounded topology
• Parity, circuits, and the polynomial-time hierarchy
• Complexity Measures for Public-Key Cryptosystems
• Relativized Polynomial Time Hierarchies Having Exactly K Levels

This page was built for publication: Structural properties for feasibly computable classes of type two