representation of monotone boolean functions
- From: sasha mal <sashaREMOVEITmal@xxxxxxxxxxxxxxxxxx>
- Date: Fri, 26 Jan 2007 19:05:10 +0100
Dear newsgroupers,
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: Hardness results for queries with preprocessing
- Next by Date: Re: Hofman and Diaby talk about P=NP at INFORMS 2007
- Previous by thread: Hardness results for queries with preprocessing
- Next by thread: a^p, p is prime
- Index(es):
Relevant Pages
|
