본 논문은 클래식 계획 문제에 대한 하한선 인증서를 소개합니다. 이 인증서는 독립적인 제3자가 검증할 수 있는 방식으로 문제의 해결 불가능성 또는 계획의 최적성을 증명하는 데 사용될 수 있습니다. 논문에서는 계획 알고리즘과 무관한 의사 부울 제약 조건을 기반으로 하한선 인증서를 생성하는 일반적인 프레임워크를 설명합니다. 사례 연구로, 패턴 데이터베이스 휴리스틱과 h<sup>max</sup>를 구체적인 예로 사용하여, 적당한 오버헤드로 최적성 증명을 생성하도록 A* 알고리즘을 수정하는 방법을 보여줍니다. 동일한 증명 로깅 방식은 의사 부울 제약 조건에 대한 추론으로 효율적으로 표현될 수 있는 모든 휴리스틱에 대해 작동합니다.