Complexity properties of recursively enumerable sets and \(bsQ\)-completeness (Q5942014)
From MaRDI portal
scientific article; zbMATH DE number 1637741
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Complexity properties of recursively enumerable sets and \(bsQ\)-completeness |
scientific article; zbMATH DE number 1637741 |
Statements
Complexity properties of recursively enumerable sets and \(bsQ\)-completeness (English)
0 references
4 March 2003
0 references
The notions of boundedly strongly effectively speedable set and boundedly effectively speedable set are introduced. It is proved that the notions of boundedly strongly effectively speedable set, boundedly effectively speedable set, creative set, and \(bsQ\)-complete recursively enumerable set are equivalent.
0 references
effectively speedable set
0 references
reducibility
0 references
recursively enumerable set
0 references
