Timeline for Relative Kolmogorov complexity
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 19, 2022 at 12:48 | answer | added | Ville Salo | timeline score: 1 | |
| Jun 18, 2022 at 6:56 | comment | added | Emil Jeřábek | @VilleSalo Perhaps you could make this an answer? | |
| Jun 18, 2022 at 5:04 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Feb 18, 2022 at 4:09 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 21, 2021 at 3:11 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Sep 21, 2021 at 3:09 | answer | added | Artemy | timeline score: 1 | |
| Sep 2, 2021 at 11:03 | comment | added | Ville Salo | Of course the result does not directly follow from that formula, $m, n$ could be long but have very low complexity. In any case suggest looking at the proof of SoI to see if it is helpful, if you did not do that already. E.g. people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf seems pretty understandable. | |
| Sep 2, 2021 at 10:20 | comment | added | Ville Salo | By symmetry of information, $K(\langle m,n \rangle) = K(n) + K_n(m) + \Theta(\log(\max(|m|,|n|)))$ (where $|m|$ is the length of the binary representation of $m$). I feel like that means the answer is no. | |
| Sep 2, 2021 at 9:55 | history | edited | Zanzi | CC BY-SA 4.0 |
added 5 characters in body
|
| S Sep 2, 2021 at 4:22 | review | First questions | |||
| Sep 2, 2021 at 5:29 | |||||
| S Sep 2, 2021 at 4:22 | history | asked | Zanzi | CC BY-SA 4.0 |