Index sets and presentations of complexity classes
type: Item
instance of: scholarly article
title: Index sets and presentations of complexity classes
zbMATH Open document ID: 0877.68058
DOI: 10.1016/0304-3975(95)00146-8
author: Kenneth W. Regan
published in: Theoretical Computer Science
publication date: 1997-09-18T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1060152
zbMATH Keywords: P-biimmune languages
MaRDI profile type: Publication
full work available at URL: 0304-3975(95)00146-8
OpenAlex ID: W2063417677
cites work: Diagonalizations over polynomial time computable sets
cites work: Q4734760
cites work: Genericity and measure for exponential time
cites work: On “provable” analogs of and
cites work: Q4039803
cites work: Bi-immune sets for complexity classes
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Q4052072
cites work: The position of index sets of identifiable sets in the arithmetical hierarchy
cites work: Index sets in the arithmetical hierarchy
cites work: On the cutting edge of relativization: The resource bounded injury method
cites work: A note on structure and looking back applied to the relative complexity of computable functions
cites work: The Expressiveness of Simple and Second-Order Type Structures
cites work: Arithmetical hierarchy and complexity of computation
cites work: The use of lists in the study of undecidable problems in automata theory
cites work: Index sets of finite classes of recursively enumerable sets
cites work: Index Sets Universal for Differences of Arithmetic Sets
cites work: Arithmetic theories for computational complexity problems
cites work: Q3744158
cites work: Recursive Predicates and Quantifiers
cites work: Indexmengen und Erkennung Rekursiver Funktionen
cites work: Relativized Polynomial Time Hierarchies Having Exactly K Levels
cites work: How to prove representation-independent independence results
cites work: On the structure of sets in NP and other complexity classes
cites work: Recursive Properties of Abstract Complexity Classes
cites work: Unprovability of theorems of complexity theory in weak number theories
cites work: Classes of Recursive Functions and Their Index Sets
cites work: Almost everywhere high nonuniform complexity
cites work: Q4153600
cites work: Reduction of an arbitrary diophantine equation to one in 13 unknowns
cites work: Hardness vs randomness
cites work: Diagonalization, uniformity, and fixed-point theorems
cites work: Computing degrees of unsolvability
cites work: Q5573961
cites work: Degrees of Unsolvability. (AM-55)
cites work: The recursion-theoretic structure of complexity classes
cites work: A uniform approach to obtain diagonal sets in complexity classes
cites work: Logical number theory I. An introduction
cites work: Q4040892
cites work: The polynomial-time hierarchy
cites work: Complete sets and the polynomial-time hierarchy
cites work: On the Degrees of Index Sets
cites work: On the Degrees of Index Sets. II
description: scientific article; zbMATH DE number 1060152