Structural properties for feasibly computable classes of type two
From MaRDI portal
Publication:4009811
DOI10.1007/BF01374524zbMath0751.68024MaRDI QIDQ4009811
Publication date: 27 September 1992
Published in: Mathematical Systems Theory (Search for Journal in Brave)
reduction; separation; polynomial hierarchy; structural complexity; extension property; pre-wellordering
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Helping by unambiguous computation and probabilistic computation, A tight relationship between generic oracles and type-2 complexity theory, Polynomial games and determinacy, Resource bounded immunity and simplicity
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