Wikipedia:Reference desk/Archives/Mathematics/2024 April 4
Mathematics desk | ||
---|---|---|
< April 3 | << Mar | April | May >> | 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
editK-triviality using conditional complexity?
editTo 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 ?), this is similar to c.e.-traceability, so I suspect it won't line up exactly with -triviality.
- For research level math like this, you'll probably have better luck on mathoverflow.--Antendren (talk) 10:04, 6 April 2024 (UTC)