AtlasFor ALignmenTOpen Atlas
← 審査済みの問い

審査済み

グラフ同型判定は多項式時間で解けるか？

Is graph isomorphism solvable in polynomial time?

computer-sciencecomputational-complexityalgorithms

問題文

2つの有限グラフが同型かどうかの判定を、多項式時間で行えるかを決定せよ。

Decide whether testing two finite graphs for isomorphism can be done in polynomial time.

背景

Graph isomorphism is the best-known problem that is neither known to be in P nor believed to be NP-complete: it sits low in the polynomial hierarchy, and Babai's quasipolynomial algorithm brought it close to, but not into, polynomial time.

アプローチ · 3 件

解決したかどうかは、問いではなくアプローチごとに決まります。Atlas は判定しません。外部の判定者が何をしたかを記録します。

  • Group-theoretic algorithms

    計算による判定

    到達状況
    進行中
    判定者
    execution and peer review: an algorithm with a proved polynomial bound settles it · 査読
    定式化
    Improve the quasipolynomial group-theoretic algorithm to a polynomial bound.問いと同値

    保たれているもの

    • A proved polynomial algorithm settles the question

    弱まっているもの

    • The current bound is quasipolynomial, which is not polynomial

    加えられた仮定・条件

    • Deep finite group theory in the analysis

    証拠

    • preprintarXiv:1512.03547L. Babai, Graph isomorphism in quasipolynomial time (2015-2016)

  • Individualization-refinement algorithms

    閉じた道（障壁）

    到達状況
    この道では到達できないと証明済み
    判定者
    none: the obstruction is a published theorem about the algorithm family · 引用

    差分（このアプローチが問いの何を保ち、何を弱めるか）はまだ書かれていません。人類審査で書きます。

    閉じた道

    • The individualization-refinement family, which covers the practical solvers, has an exponential lower bound on explicit graph families; the practical route cannot become a polynomial-time proof.無条件
      • preprintarXiv:1705.03283D. Neuen, P. Schweitzer, An exponential lower bound for individualization-refinement algorithms for graph isomorphism (2017)

  • NP-completeness

    閉じた道（障壁）

    到達状況
    この道では到達できないと証明済み
    判定者
    none: the obstruction is a published theorem · 引用

    差分（このアプローチが問いの何を保ち、何を弱めるか）はまだ書かれていません。人類審査で書きます。

    閉じた道

    • Graph isomorphism lies in the low hierarchy, so it is not NP-complete unless the polynomial hierarchy collapses; the route of proving hardness by NP-completeness is closed.条件つき（no collapse of the polynomial hierarchy）— 前提が崩れれば道は開く
      • paperdoi:10.1016/0022-0000(88)90010-4U. Schoening, Graph isomorphism is in the low hierarchy, J. Comput. System Sci. 37 (1988) 312-323: GI is not NP-complete unless the polynomial hierarchy collapses

出典

  • preprintarXiv:1512.03547L. Babai, Graph isomorphism in quasipolynomial time (2015-2016)
  • paperdoi:10.1016/0022-0000(88)90010-4U. Schoening, Graph isomorphism is in the low hierarchy, J. Comput. System Sci. 37 (1988) 312-323: GI is not NP-complete unless the polynomial hierarchy collapses

記録

URI
https://atlasalt.com/q/a4904ce1-86f2-49e3-a097-627e6a65fa65
登録
2026-09-17
最終レビュー
2026-09-19
次回レビュー期限
2026-12-18
版
ab46b38bdaae
ライセンス
CC-BY-4.0
立場
record_only（Atlas は判定しない）