Index sets and presentations of complexity classes

DOI10.1016/0304-3975(95)00146-8MaRDI QIDQ1366536zbMATH OpenOpenAlexFDO

Authors Kenneth W. Regan

Publication date 18 September 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(95)00146-8

zbMATH Keywords

P-biimmune languages

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 3873308
• Determining the levels of some special complexity classes of sets in the Kleene arithmetical hierarchy
• scientific article; zbMATH DE number 3877163
• Index sets in the arithmetical hierarchy

Cites work

• A note on structure and looking back applied to the relative complexity of computable functions
• A uniform approach to obtain diagonal sets in complexity classes
• Almost everywhere high nonuniform complexity
• Arithmetic theories for computational complexity problems
• Arithmetical hierarchy and complexity of computation
• Bi-immune sets for complexity classes
• Classes of Recursive Functions and Their Index Sets
• Complete sets and the polynomial-time hierarchy
• Computing degrees of unsolvability
• Degrees of Unsolvability. (AM-55)
• Diagonalization, uniformity, and fixed-point theorems
• Diagonalizations over polynomial time computable sets
• Genericity and measure for exponential time (extended abstract)
• Hardness vs randomness
• How to prove representation-independent independence results
• scientific article; zbMATH DE number 3979054 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 3467029 (Why is no real title available?)
• scientific article; zbMATH DE number 3586480 (Why is no real title available?)
• scientific article; zbMATH DE number 4121422 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Index sets in the arithmetical hierarchy
• Index sets of finite classes of recursively enumerable sets
• Index Sets Universal for Differences of Arithmetic Sets
• Indexmengen und Erkennung Rekursiver Funktionen
• Logical number theory I. An introduction
• On Isomorphisms and Density of NP and Other Complete Sets
• On the cutting edge of relativization: The resource bounded injury method
• On the Degrees of Index Sets
• On the Degrees of Index Sets. II
• On the structure of sets in NP and other complexity classes
• On “provable” analogs of and
• Recursive Predicates and Quantifiers
• Recursive Properties of Abstract Complexity Classes
• Reduction of an arbitrary diophantine equation to one in 13 unknowns
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• The Expressiveness of Simple and Second-Order Type Structures
• The polynomial-time hierarchy
• The position of index sets of identifiable sets in the arithmetical hierarchy
• The recursion-theoretic structure of complexity classes
• The use of lists in the study of undecidable problems in automata theory
• Unprovability of theorems of complexity theory in weak number theories

Cited in

(6)

• Index sets of classes of hyper-hypersimple sets
• Determining the levels of some special complexity classes of sets in the Kleene arithmetical hierarchy
• Classification of the index sets of low \([n]^ p\) and high \([n]^ p\)
• A second step towards complexity-theoretic analogs of Rice's Theorem
• scientific article; zbMATH DE number 3873308 (Why is no real title available?)
• On different topologies for set-indexing collections

This page was built for publication: Index sets and presentations of complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1366536)