How Does Runtime Affect the Kolmogorov Complexity of a SAT Solver's Output?

[sid_galt]

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?

Thanks

 

[CRGreathouse]

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?

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.