Sets with small generalized Kolmogorov complexity
type: Item
instance of: scholarly article
title: Sets with small generalized Kolmogorov complexity
zbMATH Open document ID: 0616.68046
DOI: 10.1007/BF00264313
author: José L. Balcázar
author: Ronald V. Book
published in: Acta Informatica
publication date: 1986-01-01T00:00:00Z
review text: We study the class of sets with small generalized Kolmogorov complexity. The following results are established: 1. A set has small generalized Kolmogorov complexity if and only if it is ''semi-isomorphic'' to a tally set. 2. The class of sets with small generalized Kolmogorov complexity is properly included in the class of ''self-p-printable'' sets. 3. The class of self-p-printable sets is properly included in the class of sets with ''self-producible circuits''. 4. A set S has self-producible circuits if and only if there is a tally set T such that \(P(T)=P(S)\). 5. If a set S has self-producible circuits, then \(NP(S)=NP_ B(S)\), where \(NP_ B( )\) is the restriction of NP( ) studied by \textit{R. Book}, \textit{T. Long} and \textit{A. Selman} [SIAM J. Comput. 13, 461-487 (1984; Zbl 0599.03041)]. 6. If a set S is such that \(NP(S)=NP_ B(S)\), then NP(S)\(\subseteq P(S\oplus SAT)\).
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3999293
zbMATH Keywords: generalized Kolmogorov complexity
zbMATH Keywords: self-producible circuits
zbMATH Keywords: tally set
MaRDI profile type: Publication
cites work: Curiouser and Curiouser: The Link between Incompressibility and Complexity
cites work: On bounded query machines
cites work: Quantitative Relativizations of Complexity Classes
cites work: On the Length of Programs for Computing Finite Binary Sequences
cites work: Information-Theoretic Limitations of Formal Systems
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Q3742716
cites work: Continuous optimization problems and a polynomial hierarchy of real functions
cites work: On Circuit-Size Complexity and the Low Hierarchy in NP
cites work: Q3214803
cites work: On Restricting the Size of Oracles Compared with Restricting Access to Oracles
cites work: A low and a high hierarchy within NP
cites work: Complexity and structure
cites work: Positive Relativizations of Complexity Classes
full work available at URL: https://doi.org/10.1007/bf00264313
OpenAlex ID: W2061746118
description: scientific article; zbMATH DE number 3999293