Polynomial clone reducibility

DOI10.1007/S00153-013-0351-XMaRDI QIDQ2436621zbMATH OpenOpenAlexFDO

Authors Quinn Culver

Publication date 25 February 2014

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10125/25920

zbMATH Keywords

algorithmic randomnesscomputabilitypolynomial clonesTuring reducibility

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Review text

In the paper under review, the author investigates randomness under polynomial clone reducibilities. The major result states that if \(x\) is Kurtz random and \(C_1\subseteq C_2\) are polynomial clones, then there is a \(y\) that is \(C_1\)-reducible to \(x\) but not \(C_2\).

Recommendations

• What can be efficiently reduced to the Kolmogorov-random strings?
• Separations by random oracles and ``almost classes for generalized reducibilities
• STACS 2004
• Strong polynomial-time reducibility
• Limitations of efficient reducibility to the Kolmogorov random strings

Cites work

• Algorithmic randomness and complexity.
• Classical recursion theory. The theory of functions and sets of natural numbers
• Comparison of linear reducibility with other reducibilities of tabular type
• Computability and randomness
• scientific article; zbMATH DE number 3961691 (Why is no real title available?)
• scientific article; zbMATH DE number 1324223 (Why is no real title available?)
• scientific article; zbMATH DE number 1390013 (Why is no real title available?)
• scientific article; zbMATH DE number 969633 (Why is no real title available?)
• Reducibility by Zhegalkin-linear tables
• Semirecursive Sets and Positive Reducibility
• Some Notions of Reducibility and Productiveness
• The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

This page was built for publication: Polynomial clone reducibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2436621)