| |
|
Science Forum Index » Math - Symbolic Forum » representation of monotone boolean functions
Page 1 of 1
|
| Author |
Message |
| sasha mal |
 Posted: Wed Jan 31, 2007 6:49 pm |
|
|
|
Guest
|
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. |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Thu Aug 21, 2008 9:38 pm
|
|
