FedSearch - Federated network search engine

I'm currently working my way through some ideas involving information theory that might have something to say about NP completeness, especially why individual problem instances are often solvable in P time but the general case is not.

In particular, there are 2**(2**k) boolean functions of k inputs, since there are 2**k distinct assignments to input variables and 2 possible outputs that that assignment might have, so you can imagine a guessing game in which Bob picks a boolean function and Alice has to guess which one it is, based on choosing some variable assignments and trying to reverse engineer the rules to gain enough Shannon entropy to identify the function. If the function is chosen uniformly, then you need 2**k bits, log2 of 2**(2**k), which sucks because the relationship between number of guesses and number of bits gained is linear.

But every boolean function can be represented by a countably infinite set of boolean formulae. Each such formula is represented by a binary tree with input variables as leaves and 2-bit boolean gates as nodes, but the number of leaves in the minimum formula is different for different functions. What if the probability of each boolean function is determined by the number of leaves in the minimal formula(e)? You could take the logarithm of the number of leaves to transform it into a "function entropy", and use that plus information theory to compute a consistent probability distribution so that low entropy functions are more likely than high-entropy functions. The guessing game then becomes a matter of Alice constructing a series of function models and then using her questions to disprove them.

That doesn't solve the problem of NP-completeness entirely, because I haven't figured out exactly how to relate the boolean function guessing game to the SAT problem yet. But it feels like a promising line of thought, since it's giving structure to the guessing step in NP's definition, and the intractability of P vs NP comes from the fact that we're treating NP instances as unstructured black boxes (which is a requirement for the standard proof technique, oracle relativization). In essence, SAT instances that are almost always true or almost always false are easy to solve because the boolean expressions involved are lower entropy, compared to SAT instances that are true or false with closer to 50/50 probability. Basically, the expression tree in the hard instances is full of XOR and XNOR operations, because those are the 2-bit boolean operations that have 50/50 truth tables, and 50/50 truth tables maximize the information entropy of the outputs over the input space.

[Here's a link to the video itself: https://youtu.be/ctwX--JEzSA ]

#UpAndAtom #ComputerScience #math #InformationTheory #InformationEntropy