Skip to main content Skip to main navigation

Publication

Fast and Exact is Doable: Polynomial Algorithms in Test and Verification

Rolf Drechsler
In: 23rd IEEE Latin-American Test Symposium (LATS). IEEE Latin American Test Symposium (LATS-2022), September 5-8, Montevideo, Uruguay, 2022.

Abstract

Ensuring the correctness of circuits and systems by test and verification is one of the central tasks in modern design flows. But most of the core algorithms have large run times, since the underlying problems can be proven to be NP- or coNP-complete. Thus, there is little hope to find efficient algorithms that can solve all instances in polynomial time and space. But recently it has been shown in the context of Polynomial Formal Verification (PFV) that for a large class of practical relevant functions fast exact algorithms can be provided. In this talk recent developments in the field of PFV are shown and directions for future work are outlined. The similarities in this domain between test and verification problems are discussed. Experimental studies show that very large designs can be handled in PFV, while fast run time can be ensured.