Jump to content

Talk:Circuit minimization for Boolean functions

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Dfass (talk | contribs) at 07:30, 19 August 2007 (→"The general problem is NP"). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

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)[reply]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Circuit_minimization_for_Boolean_functions&oldid=152203954"