랜덤 테스트는 소프트웨어 검증에 널리 사용되는 접근 방식이지만, 그 이론적 기반은 여전히 취약합니다. 특히, 주어진 입력 집합이 '생성 가능(generable)'하다는 것이 무엇을 의미하는지에 대한 근본적인 질문은 문헌과 속설 모두에서 답을 얻지 못했습니다. 본 논문에서는 소프트웨어 테스트를 위한 랜덤 생성기(random generators)의 최초의 복잡도 이론적 기초를 제시합니다. 우리는 생성기를 무작위 비트를 소비하고 문자열로 인코딩된 출력을 생성하는 튜링 변환기(Turing transducers)로 모델링하고, 이론적으로 생성 가능한 언어들이 재귀적으로 열거 가능한 언어(recursively enumerable languages)와 정확히 일치함을 보여줍니다. 이는 컴파일러 테스트와 같이 결정 가능성(decidability)의 경계에서 이루어지는 테스트에 직접적인 영향을 미칩니다. '효율적(efficient)' 생성을 위해, 우리는 다항 시간(polynomial-time)으로 생성 가능한 언어들이 $ extit{NP}$ 안에 존재하며, 특정 $ extit{NP}$-완전(complete) 언어들이 효율적인 생성기를 허용하고, 표준 암호학적 가정 하에서는 $ extit{P}$에 속하지만 효율적인 생성기가 존재하지 않는 언어들도 있음을 보여줍니다. 즉, 효율적인 생성의 복잡도와 효율적인 결정의 복잡도는 같지 않습니다. 우리는 공간 제한된 복잡도(space-bounded complexity)가 '상관관계가 있는(correlated)' 샘플을 생성하는 생성기들의 자연스러운 프레임워크임을 보여주며, 이는 커버리지 기반 퍼징(coverage-guided fuzzing)이나 심볼릭 실행(symbolic execution)과 같은 방법론들을 포괄합니다. 분류를 넘어, 우리는 효율적인 생성 가능성을 특성화합니다: 어떤 언어가 다항 시간 생성기를 가지려면 검증기(verifier)에 대한 '인증서 방식(certificate scheme)'을 허용해야 합니다. 따라서 SAT 솔버 테스트를 위한 생성기의 배경이 되는 속설적 기법인 증인 배치(witness planting)는 일종의 효율적인 생성을 위한 유일한 경로입니다. 속성 기반 테스트 라이브러리의 설계에 관하여, 우리는 표준 가정 하에서 논리적 술어(logical predicates)에 포함된 논리곱(conjunction)이나 부정(negation)으로부터 어떤 라이브러리도 구성적으로 효율적인 생성기를 도출할 수 없음을 증명합니다. 다만, $ extit{NL}$과 같은 제한된 클래스(이는 선형 Datalog 술어와 동등함)는 그러한 컴파일을 허용할 것입니다.