Quasi-completeness and functions without
β
Ilnur I. Batyrshin
π
Article
π
2006
π
John Wiley and Sons
π
English
β 131 KB
## Abstract We prove a completeness criterion for quasiβreducibility and generalize it to higher levels of the arithmetical hierarchy. As an application of the criterion we obtain Qβcompleteness of the set of all pairs (__x__, __n__) such that the prefixβfree Kolmogorov complexity of __x__ is less