Talk:Circuit minimization

From Wikipedia, the free encyclopedia

[edit] "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)

Apologies. It's not my field, and I just wrote it off the top of my head (from some dim memory). I changed it now to something possibly better, although I'm hoping that someone who knows the field will swoop in and make it into a real article. —Dfass 07:30, 19 August 2007 (UTC)

[edit] Addition of purpose and example

I decided to add the "purpose" section to clarify the reason why anyone would want to minimize a circuit in the first place. I also added an example for a circuit using boolean logic and showed that it can be simplified to an XOR gate (the picture was drawn by me, and I think the 'or' and 'xor' gates should be a bit more pointy at the edge but I couldn't draw it so well). Uoft ftw (talk) 00:44, 13 February 2008 (UTC)