- #1

- 502

- 1

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