1-3
그래프 동형
graph isomorphism
두 그래프가 점의 이름만 다르고 모양은 같은지 묻는 문제
한 그래프의 꼭짓점 이름을 바꿔 다른 그래프와 똑같이 만들 수 있는지 묻는다. 이름을 바꾸는 대응이 증거가 되므로 NP 에 속한다. 그러나 P 에 속하는지도 NP-완전인지도 알려져 있지 않다. 바바이가 2015년에 준다항 시간(2^((log n)^c) 꼴) 알고리즘을 발표했다. 이 문제가 NP-완전이면 다항 위계가 무너진다는 결과가 있어 NP-완전은 아닐 것으로 여겨지며, 인수분해와 함께 NP-중간의 대표 후보다.