I haven't thought about how to go about proving it or finding a counterexample (I probably don't have the right background), but it seems intuitive to me that, given some representation of a Boolean function, say sum of products, the minimal SOP expression is somehow related to the Kolmogorov Complexity of the binary string representation. I've done some searching but can't find anything. If you don't know of a relationship but know of related references, please share.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The relationship is that a short SOP expression implies a low Kolmogorov complexity, but not vice versa. If you have a short SOP expression, then that is a concise way to compress the string, hence Kolmogorov complexity is low. However, there might be strings that can be compressed in another way even though the SOP expression is long, and those strings would have a low Kolmogorov complexity but a large SOP expression.
-
$\begingroup$ (I accidentally hit enter previously) I don't know the definitions involved here very well, but is there any way in which the SOP representation of Boolean functions could be considered a sort of Turing complete language (I assume so since it can obviously represent XOR)? Maybe I should have been more specific, but the relationship you provide is trivial. If what I wrote above is true (and thus we don't have to assume that I am somehow "implementing" SOP in another language), it may not even be quite correct since the KC is dependent on the language chosen to construct the program. $\endgroup$ Jan 11, 2022 at 21:47
-
$\begingroup$ What I would really like to know is if there are some bounds on the degree of optimality or something. $\endgroup$ Jan 11, 2022 at 21:48