3 ms·
This discussion is about monotone Boolean functions. That is, functions from {0,1}^N → N, such that "flipping" any input from 0 to 1 never causes the output to
by teraflop 3y ago
This discussion is about monotone Boolean functions. That is, functions from {0,1}^N → N, such that "flipping" any input from 0 to 1 never causes the output to go from 1 to 0.
I can't think of any way to to write a prime-counting function as an interesting monotone Boolean function. If you represent the numbers in binary, it's not monotone. If you write them in unary, with a separate function for each bit, then each bit's function (taken by itself) is just a near-trivial threshold function.
- teraflop 3y agoD'oh -- I meant {0,1}^N → {0,1}, but it's too late to edit my previous comment.
- jacquesm 3y agoNo worries, I got that. Boolean came before programming for me by way of electronics. Which is what I thought was interesting about this article, to imagine the algorithm but as discrete logic.