Talk:Circuit minimization for Boolean functions

"The general problem is NP"

The article currently says

The general problem is NP, but there are effective heuristics such as Karnaugh maps and the Quine–McCluskey algorithm that facilitate the process.

I don't think what is literally stated here can possibly be what is intended. Saying that a problem is NP is an assertion that it's not harder than a certain level of difficulty, not that it's at least that hard. The problem of deciding whether zero equals zero is NP.

Probably what is intended here is that the problem is NP-hard, or perhaps NP-complete (which means both NP-hard and NP). Another slim possibility is that it means something like "the problem is NP, and if the polynomial-time heirarchy does not collapse, then the problem is not P". I don't know enough about the problem to say which of these is the intended meaning. Someone who does, please clarify. --Trovatore 06:43, 19 August 2007 (UTC)