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[edit]
K-triviality using conditional complexity?[edit]
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 ?), 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)
