The Complexity Landscape of Boolean Formula Isomorphism: From Graph Isomorphism to the Second Level
이 논문은 정형적 공식 동형성(canonical formula isomorphism)과 그래프 동형성(graph isomorphism) 사이의 양방향 다대일 등가성을 확립함으로써 불리언 공식 동형성의 복잡도를 다항 계층 내에서 정밀하게 분류하며, 일반적인 공식 동형성이 coNP-완전인 동치성 테스트와 잔여 그래프 동형성 핵심의 결합으로 인해 제2계층()에 존재함을 입증한다.