Information on time-complexity prior?

post by Garrett Baker (D0TheMath) · 2021-01-08T06:09:03.462Z · LW · GW · No comments

This is a question post.

Contents

  Answers
    11 DanielFilan
None
No comments

On a recent episode of The Bayesian Conspiracy, the time-complexity prior was mentioned as a plausible alternative to Solomnoff induction. And reading Abram Demski's explanation of logical induction in Toward a New Technical Explanation of Technical Explanation [LW · GW], a prior over time-complexity seems like a natural consequence of the formulation.

Can anyone provide sources for more information on this, assuming such sources exist?

Answers

answer by DanielFilan · 2021-01-08T19:09:30.708Z · LW(p) · GW(p)

Two relevant papers:

You probably also want to know about Kt complexity, called Levin complexity here, which I believe is covered in Li and Vitányi's textbook on Kolmogorov complexity.

No comments

Comments sorted by top scores.