representation of monotone boolean functions
- From: sasha mal <sashaREMOVEITmal@xxxxxxxxxxxxxxxxxx>
- Date: Fri, 26 Jan 2007 19:00:06 +0000 (UTC)
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
in n but needs asymptotically less than 2^n bits?
Best regards
sasha.
.
- Prev by Date: minimal distance to an affine subspace
- Next by Date: Re: minimal distance to an affine subspace
- Previous by thread: minimal distance to an affine subspace
- Next by thread: a query on Laplace transform on the complex plane
- Index(es):
Relevant Pages
|
