Determining whether a digital circuit is optimal - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-23T15:48:09Z https://cs.stackexchange.com/feeds/question/49250 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/49250 2 Determining whether a digital circuit is optimal Alan Wolfe https://cs.stackexchange.com/users/38039 2015-11-09T00:34:25Z 2015-11-09T03:56:15Z <p>Are there any techniques that can be used to determine whether a digital logic circuit is optimal, or if it has extraneous operations that don't contribute to the output?</p> <p>I'm especially curious in the case where the circuit is defined in terms of XOR and AND gates.</p> <p>I know I could make a karnaugh map and create a circuit from that, but that doesn't really tell me about the circuit I had, it just gives me another circuit.</p> <p>Thanks for any info!</p> https://cs.stackexchange.com/questions/49250/-/49252#49252 3 Answer by D.W. for Determining whether a digital circuit is optimal D.W. https://cs.stackexchange.com/users/755 2015-11-09T03:56:15Z 2015-11-09T03:56:15Z <p>Use one of the standard techniques for <a href="https://en.wikipedia.org/wiki/Circuit_minimization_for_Boolean_functions" rel="nofollow">circuit minimization</a>. As far as I know, verifying that a candidate circuit is minimal is as hard as finding the minimal circuit in the first place (I know of no faster algorithm for verifying minimality than finding a minimal circuit in the first place).</p> <p>Circuit minimzation is NP-hard (in fact it's even harder than that, in some sense), so you shouldn't expect an efficient algorithm for it that handles all functions efficiently.</p>