Re: representation of monotone boolean functions

On 31 jan, 20:49, "sasha mal" <sasha.REMOVEIT...@xxxxxxxxxxxxxxxxxxxx>
wrote:
Dear all,

as we all know, the number of monotone Boolean functions on n variables
is less than or equal to 3^binom(n,[n/2]). Please correct me if I'm
wrong. So for encoding of a monotone function binom(n,[n/2])*(log_2 3)
bits should suffice, which is asymptotically less than 2^n. Is there an
encoding that allows evaluating a monotone function in polynomial time (on a
RAM with logarithmic cost measure)
in n but needs asymptotically less than 2^n bits?

Best regards
sasha.


.

Relevant Pages