>>> Basically, a very optimistic hope for understanding “why circuits behave differently from functions” is to make statements that, conditional on some “surprising” property P holding for a circuit (here “surprising” means that it occurs much more for circuits than functions), we can deduce that, with high probability, the circuit internals have some property A(C).
My understanding of the NCP-conjecture is different [and I claim more interesting].
If we want we can go from a surprising property Q [your P] holding for the function to some property A(C)… the canonical way is to assume some probability model and do Bayesian updating.
In other words A(C) will be some averaged property over the Bayesian posterior. Assuming everything is discrete and finite [we work with Boolean circuit of fixed size] and a uniform prior this is all completely explicit.
The more interesting thing to me is the following.
Let’s say Q is a disjunction Q = Q_1 OR Q_2
In that case, informally we could reason: well Q is the case because either Q_1 is the case or Q_2 is the case. Crucially the property A(C) holding for the underlying circuit C may depend on whether we have Q_1 or Q_2.
Just like we can have many different proofs for the truth of the same statements more generally we can have many different heuristic arguments for the same ‘truish’ proposition. The Bayesian posterior almagates and averages over all of them.
-------
Random Speculations:
Let me speculate on what an heuristic argument may be in this case.
One proposal for what a heuristic argument would be is the following:
parameterize probability distributions on the finite discrete space of Boolean circuits and Boolean functions by an exponential family [iiuc this can be done using log-linear models]. Then consider the outrageous statement Q(C) and consider those distributions that make it very likely.
In other words if we parameterize our distributions by w then P(Q(C)|w) is assumed high. For a given C and a specific w we may ask is P(C|w) high or even equal to 1? In that case, that w and the associated sufficient statistics may be regarded as a reason for Q(C).
of course—there are many such w potentially. We need w that are not too complicated to describe for each possible circuit C.
Let’s look at the fiber F=F^{-1}(Q)=\{C\in Circuit| Q(C)\}. Now the fiber F breaks up in components F_i—intuitively there are different classes of fuctions/circuits that can give rise to the property Q. We’re looking for simple descriptions / sufficient statistics w such that of a given component F_i is assigned high probability by w.
How do we find these components F_i—if they even make sense? One way is to recursively break up the fiber of F of Q=Q(C) by logically decomposing Q and using subformulas to describe boolean features that may fix a sufficient statistic for above.
>>> Basically, a very optimistic hope for understanding “why circuits behave differently from functions” is to make statements that, conditional on some “surprising” property P holding for a circuit (here “surprising” means that it occurs much more for circuits than functions), we can deduce that, with high probability, the circuit internals have some property A(C).
My understanding of the NCP-conjecture is different [and I claim more interesting].
If we want we can go from a surprising property Q [your P] holding for the function to some property A(C)… the canonical way is to assume some probability model and do Bayesian updating.
In other words A(C) will be some averaged property over the Bayesian posterior. Assuming everything is discrete and finite [we work with Boolean circuit of fixed size] and a uniform prior this is all completely explicit.
The more interesting thing to me is the following.
Let’s say Q is a disjunction Q = Q_1 OR Q_2
In that case, informally we could reason: well Q is the case because either Q_1 is the case or Q_2 is the case. Crucially the property A(C) holding for the underlying circuit C may depend on whether we have Q_1 or Q_2.
Just like we can have many different proofs for the truth of the same statements more generally we can have many different heuristic arguments for the same ‘truish’ proposition. The Bayesian posterior almagates and averages over all of them.
-------
Random Speculations:
Let me speculate on what an heuristic argument may be in this case.
One proposal for what a heuristic argument would be is the following:
parameterize probability distributions on the finite discrete space of Boolean circuits and Boolean functions by an exponential family [iiuc this can be done using log-linear models]. Then consider the outrageous statement Q(C) and consider those distributions that make it very likely.
In other words if we parameterize our distributions by w then P(Q(C)|w) is assumed high.
For a given C and a specific w we may ask is P(C|w) high or even equal to 1?
In that case, that w and the associated sufficient statistics may be regarded as a reason for Q(C).
of course—there are many such w potentially. We need w that are not too complicated to describe for each possible circuit C.
Let’s look at the fiber F=F^{-1}(Q)=\{C\in Circuit| Q(C)\}.
Now the fiber F breaks up in components F_i—intuitively there are different classes of fuctions/circuits that can give rise to the property Q. We’re looking for simple descriptions / sufficient statistics w such that of a given component F_i is assigned high probability by w.
How do we find these components F_i—if they even make sense? One way is to recursively break up the fiber of F of Q=Q(C) by logically decomposing Q and using subformulas to describe boolean features that may fix a sufficient statistic for above.