The paper "Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses" <http://www.itu.dk/people/pagh/papers/sparse.pdf> is the only one that uses Kolmogorov Complexity to obtain a lower bound in the space of a data structure that rank with erros.

My question is: What are the other Algorithmic options of complexity that replace the Kolmogorov Complexity? Is Kolmogorov-Sinai Entropy a option?

  • 1
    $\begingroup$ Can you clarify what you mean by "algorithmic options of complexity"? $\endgroup$ – D.W. Aug 9 '16 at 7:47
  • $\begingroup$ Kolmogorov Complexity ins't computable and is the "ultimate lower bound to space analysis" according to "Squeezing succinct data structures into entropy bounds" <<semanticscholar.org/paper/…>>. There is no detailed (to my knowledge) detailed study in space analysis of data structures using Kolmogorov Complexity or a COMPUTABLE VERSION of Complexity, an algorithmic complexity. $\endgroup$ – Ricardo S. Aug 9 '16 at 8:04
  • $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. $\endgroup$ – Raphael Aug 9 '16 at 8:24
  • $\begingroup$ Do you know any computable cost/complexity measure? The typical $O$-runtime certainly is not. $\endgroup$ – Raphael Aug 9 '16 at 8:25
  • $\begingroup$ Time-bounded Kolmogorov Complexity is a computable upper bound for prefix-free Kolmogorov complexity. Read the article "Time-Bounded Kolmogorov Complexity and Solovay Functions" link.springer.com/article/10.1007/s00224-012-9413-4 $\endgroup$ – Ricardo S. Aug 23 '16 at 4:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.