Jul 2026
Complexity Theory of Randomised Testing
This work presents the first complexity-theoretic foundations for random generators in software testing, and characterise efficient generability: a language has a polynomial-time generator iff it admits a \emph{certificate scheme} over a verifier, so witness planting is in a sense the only route to efficient generation...
Ping-Shi Yu, Cheng-Song Tan, Nicolas Wu et al.
· arXiv.org · 0 citations