Hacker News new | ask | show | jobs
by joe_the_user 4569 days ago
While it's nice learn De Morgan's Law if you don't know it, it occurs to me that the problem of finding the simplest version of a given logical expression in n logical variables is a classic NP-complete problem (or NP-hard, the simpler question of whether the negation of an expression can be reduced to true is basically SAT).

There is no easy method to reduce every expression to a simple normal form - the conjunctive normal form of a given be exponentially larger than the original expression, etc.