Technology dependent logic optimization is usually carried through a sequence of design rewiring operations. In [18] a new design rewiring method is proposed that combines error diagnosis and correction techniques with ATPG. In this work, we examine its complexity and we arrive to a new set of results with interesting theoretical and practical applications. We also present experiments that confirm the competitiveness of the approach and motivate future work in the field.