Q. How do your results relate to the current perception of EC?
A.The common perception of EC in the engineering community is that if circuits N and N* are similar, one can use this similarity to help solve this instance. (For example, one can try to indentify functionally equivalent internal points or by use some rewriting techniques.) By finding new heuristics, one can attack more and more complex EC problems and so "make progress". On the other hand, if circuits N and N* are not "similar", then their EC is "naturally hard".
Our results question this perception. One can make circuits aribitrarily "close" and still make efficient EC of N and N* infeasible. (The closeness of N and N* is measured by the value of granularity(Spec(N)) ⁄ |N| and
granularity(Spec(N*)) ⁄ |N*| . The smaller these two ratios are for N and N* , the closer these circuits are structurally). If our assumption is true (that the complexity of EC ofN and N* is exponential in the granularity of their common speciification), no "gradual" progress in EC is possible. By making granularity of Spec(N) and Spec(N* slightly larger, one can eliminate any such progress. Importantly, circuits N and N* with a common specification are definitely structurally similar (because they can be partitioned into toggle equivalent subcircuits connected in the same way). The fact that their EC can not be done efficently (unless specifications N and N* are known) implies that in this case, EC is an "unnaturally hard" problem.