유효한 테스트 입력인지 판정하는 일과 그 입력을 실제로 무작위 생성하는 일은 계산적으로 같은 문제가 아니다. 단순히 어떤 입력이 유효한지 판정하는 문제와, 그 입력 공간을 실제로 표본화하는 문제를 분리하고 시간·공간 제한 아래 생성 가능한 언어 클래스를 분석했다.
논문은 경험적 퍼저 순위표가 아니라 정리와 환원으로 구성된 이론 연구다. 무제한 생성, 다항시간 생성, 상관된 표본을 만드는 공간 제한 생성, 논리 술어에서 생성기를 조합하는 라이브러리 설계를 차례로 다룬다. SAT 해를 미리 심는 관행도 인증서 체계의 사례로 재해석한다.
제약 없는 의미에서 생성 가능한 언어는 재귀적으로 열거 가능한 언어와 정확히 일치한다. 다항시간 생성 가능 언어는 NP 안에 있지만, 표준 암호 가정 아래 P에 속하면서 효율적 생성기가 없는 언어도 존재한다고 보였다. 효율적 생성은 검증기 위 인증서 체계가 존재하는 경우와 동치라는 특성화도 제시한다.
결과는 속성 기반 테스트·컴파일러 퍼징·기호 실행 도구가 유효 입력을 어떻게 만들 수 있는지에 이론적 경계를 준다. 상관 표본에는 공간 복잡도가 자연스러운 틀이라는 분석은 커버리지 유도 퍼징의 상태 보존을 설명한다. 특정 라이브러리의 실제 결함 탐지율을 예측하는 모델은 아니다. 부정이나 논리곱을 포함한 임의 술어에서 효율적 생성기를 조합하는 범용 라이브러리는 표준 가정 아래 불가능하다는 제한도 제시한다. 다만 NL처럼 제한된 클래스에는 조합 가능성이 남는다.
이 경계는 arXiv:2607.11811에 공개된 심사 전 이론 결과다. 정리의 형식적 전제와 실제 프로그램 표현의 대응은 구현마다 따져야 하며, 특정 퍼저의 결함 탐지율을 직접 예측하지 않는다.
저작권자 © STORIUM 무단전재 및 재배포 금지
