Classification of the index sets of low [n]^ p and high [n]^ p

DOI10.1007/BF02945518MaRDI QIDQ1337641zbMATH OpenOpenAlexFDO

Authors Yuefei Sui

Publication date 19 September 1995

Published in Journal of Computer Science and Technology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02945518

zbMATH Keywords

index setspolynomial enumerable sets

Mathematics Subject Classification ID

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

Recommendations

• On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
• On the topological size of p-m-complete degrees
• Index sets and presentations of complexity classes
• Hyperarithmetical Index Sets in Recursion Theory
• Index sets in the arithmetical hierarchy

Cites work

• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3562522 (Why is no real title available?)
• A hierarchy for nondeterministic time complexity
• Alternation
• Computational complexity, speedable and levelable sets
• The NP-completeness column: An ongoing guide

Cited in

(2)

• Index sets for ^0_1 classes
• Index sets of classes of hyper-hypersimple sets

This page was built for publication: Classification of the index sets of low \([n]^ p\) and high \([n]^ p\)

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