Key points are not available for this paper at this time.
그래프 동형성 문제는 그 복잡도 상태를 결정하려는 시도에도 불구하고 지금까지 저항해 왔습니다—이 문제는 NP-완전임이 증명되지 않았고 P에도 속하지 않습니다. 이 논문에서는 동형성 문제의 여러 변형 또는 일반화된 버전을 제시하고 이들이 NP-완전임을 보입니다. 이 중 하나는 주어진 그래프가 고정점 없는 자동 동형성을 가지는지 여부를 결정하는 문제입니다. 이러한 결과가 동형성의 복잡도 상태를 결정하는 데 미칠 수 있는 의미에 대한 몇 가지 추측이 제기됩니다. NP에서의 여러 문제의 클래스와 계층이 논의됩니다.
안나 루비우 (Anna Lubiw)가 이 질문을 연구했습니다.