Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Kolmogorov complexity of SAT

  1. Sep 28, 2008 #1
    I'm not entirely clear on the concept of kolmogorov complexity. Does it mean that the a certain string is complex if there is no combinatorial (not sequential) circuit which outputs that string or does it mean that a certain string is complex if there is no program which can output that string.

    For instance, it is relatively easy to encode a SAT solver (for instance the DPLL algorithm). What would the kolmogorov complexity of the output string of this solver. Would it be extremely high because the solver requires exponential runtime or would it be low because the program to encode the solver is pretty small?

  2. jcsd
  3. Sep 29, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    The Kolmogorov complexity of a string is no more than the size of a program that generates it (along with the input, if any, needed by the program). Runtime is irrelevant.

    The complexity could be less if there is a shorter program that generates the string.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook