Refinment of the "up to a constant" ordering using contructive co-immunity and alike. Application to the Min/Max hierarchy of Kolmogorov complexities

Simple item page
dc.creatorFerbus-Zanda, Marie
dc.creatorGrigorieff, Serge
dc.date2008-01-02
dc.date.accessioned2026-07-07T08:52:32Z
dc.date.available2026-07-07T08:52:32Z
dc.descriptionWe introduce orderings between total functions f,g: N -> N which refine the pointwise "up to a constant" ordering <=cte and also insure that f(x) is often much less thang(x). With such orderings, we prove a strong hierarchy theorem for Kolmogorov complexities obtained with jump oracles and/or Max or Min of partial recursive functions. We introduce a notion of second order conditional Kolmogorov complexity which yields a uniform bound for the "up to a constant" comparisons involved in the hierarchy theorem.
dc.description41 pages
dc.identifierhttps://arxiv.org/abs/0801.0350
dc.identifierhttp://arxiv.org/abs/0801.0350
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/145312
dc.subjectLogic
dc.subjectComputational Complexity
dc.titleRefinment of the "up to a constant" ordering using contructive co-immunity and alike. Application to the Min/Max hierarchy of Kolmogorov complexities
dc.typetext

Files

Collections

arXiv