A Class of Polynomially Verifiable Circuits of Logarithmic Depth
Caroline Dominik, Rolf Drechsler · 2023
Formal verification is central to fully ensure the functional correctness of logic circuits. However, since formal methods often have high resource demands, not all circuits can be verified efficiently. Some use cases cannot be inspected due to memory or time constrictions. Out of this circumstance the field of Polynomial Formal Verification (PFV) has emerged. The goal of PFV is to ensure that a circuit or a class of circuits can be verified efficiently. This is done by calculating polynomial upper bounds for the resource demands of the verification process.In this paper we contribute to this approach by investigating the formal verification of a class of circuits with logarithmic depth. It is proven that the used resources stay polynomial during the entire verification process and this proof is confirmed with experiments. Moreover, it is shown that practical use cases do not exhaust the calculated upper bounds.