2014 January 12
originally posted on facebook

Here’s a generalization of a puzzle about logic gates I posted in July, which (if you are one of the roughly two people who solved it) neatly explains how the puzzle works. (The original source I saw for this puzzle claimed further that any boolean function could be computed by a logic circuit using only two not gates, which I now think is unlikely to be true as this article demonstrates a solution requiring O(log(n)) not gates for a function with n inputs, and I think one might easily show that the solution in the article is optimal.)


Follow RSS/Atom feed or twitter for updates.