representation of monotone boolean functions
- From: "sasha mal" <sasha.REMOVEITmal@xxxxxxxxxxxxxxxxxxxx>
- Date: Wed, 31 Jan 2007 23:49:30 +0100
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.
.
- Next by Date: Re: How do I make a CAS be creative?
- Next by thread: Re: How do I make a CAS be creative?
- Index(es):
Relevant Pages
|
