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.(adsbygoogle = window.adsbygoogle || []).push({});

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?

Thanks

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Kolmogorov complexity of SAT

**Physics Forums | Science Articles, Homework Help, Discussion**