Sets with small generalized Kolmogorov complexity (Q1821559): Difference between revisions

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)\).