Complexity properties of recursively enumerable sets and bsQ-completeness

DOI10.1007/BF02676727MaRDI QIDQ5942014zbMATH OpenOpenAlexFDO

Authors Roland Sh. Omanadze

Publication date 4 March 2003

Published in Mathematical Notes (Search for Journal in Brave)

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

zbMATH Keywords

reducibilityrecursively enumerable seteffectively speedable set

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Complexity properties of recursively enumerable sets and sQ-completeness
• scientific article; zbMATH DE number 1138314
• On \(sQ\)-completeness of recursively enumerable sets
• DEFINABILITY OF RECURSIVELY ENUMERABLE SETS IN ABSTRACT COMPUTATIONAL COMPLEXITY THEORY
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• scientific article; zbMATH DE number 3914303
• scientific article; zbMATH DE number 3896921
• Kolmogorov complexity and computably enumerable sets
• Computably enumerable sets and quasi-reducibility
• Complete sets and closeness to complexity classes

Cites work

• scientific article; zbMATH DE number 3733888 (Why is no real title available?)
• scientific article; zbMATH DE number 1232433 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Complexity properties of recursively enumerable sets and sQ-completeness
• ON WAYS OF CHARACTERIZING COMPLETE SETS
• On complexity properties of recursively enumerable sets
• On subcreative sets and S-reducibility
• Reducibility and Completeness for Sets of Integers

Cited in

(3)

• scientific article; zbMATH DE number 1138314 (Why is no real title available?)
• Irreducible, singular, and contiguous degrees
• Implicit measurements of dynamic complexity properties and splittings of speedable sets

This page was built for publication: Complexity properties of recursively enumerable sets and \(bsQ\)-completeness

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