Talk:Circuit minimization for Boolean functions: Difference between revisions

Revision as of 06:43, 19 August 2007

Latest revision as of 12:50, 24 December 2024

(13 intermediate revisions by 9 users not shown)

Line 1:

{{WikiProject banner shell|

{{WikiProject Mathematics}}

{{WikiProject Computing|importance=}}

}}

{{merged-to|Logic optimization|date=14 September 2017}}

== "The general problem is NP" ==

Line 6 ⟶ 12:

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. --[[User:Trovatore|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. —[[User:Dfass|Dfass]] 07:30, 19 August 2007 (UTC)

== 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). [[User:Uoft ftw|Uoft ftw]] ([[User talk:Uoft ftw|talk]]) 00:44, 13 February 2008 (UTC)