Testwiki:Reference desk/Archives/Mathematics/2024 April 4

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < April 3 ! width="25%" align="center"|<< Mar | April | May >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 4

K-triviality using conditional complexity?

To account for length, the definition of K-trivial set makes the complexity of the length part of the upper-bound on the complexity of the string. Has anyone determined what happens if one instead asks for a bound on the length-conditional complexity? This could be done with either plain or prefix-free Kolmogorov complexity. JumpDiscont (talk) 00:12, 4 April 2024 (UTC)

If there's a constant bound on the length-conditioned complexity, then the set is computable. For a bound that tends to infinity (maybe $K(n)$?), this is similar to c.e.-traceability, so I suspect it won't line up exactly with $K$-triviality.

For research level math like this, you'll probably have better luck on mathoverflow.--Antendren (talk) 10:04, 6 April 2024 (UTC)