본 논문은 신경 기호 인공지능(NeSy AI) 시스템의 확률적 추론의 강건성을 공식적으로 검증하는 문제를 다룬다. NeSy AI는 신경망 학습과 기호적 추론을 통합하는 유망한 방향으로, 일반적으로 신경망이 하위 기호 입력에서 기호 집합을 추출하고, 이를 기호적 구성 요소가 사용하여 확률적으로 추론하여 질의에 답하는 방식이다. 본 논문에서는 이러한 NeSy 확률적 추론 시스템의 강건성 검증의 복잡성을 분석하고, 핵심 계산의 결정 문제가 NP<sup>PP</sup>-완전함을 보인다. 이러한 결과를 바탕으로, 확률적 NeSy 시스템의 근사적이고 완화 기반의 검증을 위한 최초의 접근 방식을 제안하고, 표준 NeSy 벤치마크에서 제안된 방법이 솔버 기반 솔루션보다 기하급수적으로 더 잘 확장됨을 실험적으로 보여주며, 고차원 입력에서 안전 속성을 검증하는 실제 자율 주행 영역에 기술을 적용한다.
