실제로, 여기서의 현상은 어떤 의미에서 GI가 너무 많은 구조를 가지고 있다는 것 입니다. 그것은 몇 가지 방법에 리드의 증인의 그룹 이론적 성격이다 사람들이 GI가 아닌 생각하는 이유를 기술 증거의 조각 중 하나입니다 GI에 대한 알고리즘과 N P의 – 완전한. 여기에 내 생각은 문제가 인코딩 임의에 “너무 경직”입니다 너무 많은 구조 있다는 것입니다 N P의 문제.c o A M

$\mathsf{coAM}$NP

$\mathsf{NP}$NP

$\mathsf{NP}$

이 캡처하는 또 다른 방법은 GI의 계산 및 의사 결정 버전, 동일 사실이다 반면에 알려진 모든에 대한 NP

$\mathsf{NP}$ 다항식 계층 구조가 붕괴되지 않는 한 – 완전한 문제이 경우는 없습니다. 이것은 구조 / 이중화의 일부 측면을 포착하는 것으로 볼 수도 있습니다. 구조화되지 않은 일반적인 문제의 경우 계수 솔루션은 존재하는지 확인하는 것보다 훨씬 어려워 보이지만 GI의 광범위한 구조는 계수와 결정이 동등하다는 것을 보여줍니다.

(반면, 그룹 동 형사상은 GI보다 훨씬 더 구조화 된 것처럼 보이지만 그룹 이소에 대한 계수 결정 감소는 알려져 있지 않습니다. 아마도 이것은 GI가 일종의 “정확한”수준의 구조에 있다고 말합니다. NP- 완료되었지만 계산에서 계산을 줄일 수있을 정도로 구조화되지 않은 상태 여야합니다.)

답변