1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Kolmogorov complexity of SAT
  1. Weird sat (Replies: 11)

  2. Sat Help (Replies: 8)

  3. Sat question (Replies: 3)