コンピュータサイエンスにおける未解決問題のリスト

この記事は、コンピュータ科学における注目すべき未解決問題の一覧です。コンピュータ科学における問題は、解決策が知られていない場合、または当該分野の専門家の間で提案された解決策について意見が分かれている場合に、未解決問題とみなされます。

• P対NP問題– P対NP問題は、コンピュータサイエンスにおける未解決の大きな問題であり、コンピュータによって迅速に検証できる問題（NP）はすべて、コンピュータによって迅速に解決できる問題（P）でもあるかどうかを問うものです。この問題は、暗号、アルゴリズム設計、計算理論などの分野に大きな影響を与えます。^{[ 1 ]}
• BQPとNPの関係は何ですか？
• NC = P問題
• NP = co-NP問題
• P = BPP問題
• P = PSPACE問題
• L = NL問題
• PH = PSPACE 問題
• L = P 問題
• L = RL問題
• ユニークなゲーム予想
• 指数時間仮説は正しいのか？
  • 強い指数時間仮説（SETH）は正しいのか？
• 一方通行関数は存在するのか？
  • 公開鍵暗号方式は可能でしょうか？
• ログランク予想
• ハートマニス・スターンズ予想

• 整数因数分解は、古典的（非量子）コンピュータ上で多項式時間で実行可能か？
• 離散対数は、古典的（非量子）コンピュータ上で多項式時間で計算できるだろうか？
• 格子の最短ベクトルは、古典コンピュータまたは量子コンピュータ上で多項式時間で計算できるだろうか？
• グラフ同型性問題は、古典コンピュータ上で多項式時間で解けるだろうか？

グラフ同型性問題とは、2 つの有限グラフが同型であるかどうか、つまり、それらの頂点と辺の間に隣接関係を保持する 1 対 1 の対応関係が存在するかどうかを判定する問題です。この問題は NP に属することが知られていますが、NP 完全であるか、多項式時間で解けるかどうかはわかっていません。この不確実性により、この問題は独自の複雑性クラスに分類され、コンピュータ サイエンスにおける重要な未解決問題となっています。^{[ 2 ]}

• グラフの正準化問題は、グラフ同型性問題と多項式時間で同等でしょうか？
• 葉のべき乗とk葉のべき乗は多項式時間で認識できますか？
• パリティゲームは多項式時間で解けるか？
• 2つの二分木間の回転距離を多項式時間で計算することは可能か？
• 有界クリーク幅のグラフは多項式時間で認識できるか？^{[ 3 ]}
• 凸多面体上の単純な閉じた準測地線を多項式時間で見つけることは可能か？ ^{[ 4 ]}
• 与えられた 2 つのグラフに対して、固定エッジを用いた同時埋め込みを多項式時間で見つけることは可能か？ ^{[ 5 ]}
• チューリングマシンモデルにおいて、平方根和問題は多項式時間で解けるか？

• スコレム問題：代数的な線形漸化式に零点が存在するかどうかを判定できるか？
• 有理数体におけるヒルベルトの第10問題

• 動的最適性予想：スプレッドツリーは有界な競争比率を持つのか？
• NCで深さ優先探索木を構築することは可能ですか？
• 高速フーリエ変換は、o ( n log n )の時間で計算できますか？
• n桁の2つの数を掛け合わせるための最速のアルゴリズムは何ですか？
• 決定論的な固定ギャップシーケンスを用いたシェルソートの平均時間計算量の最小値はどれくらいですか？
• 3SUMは、強い劣二次時間、つまり、あるε > 0に対してO ( n ^2−ε )の時間で解くことができるか？
• 長さnの2つの文字列間の編集距離を、強い準二次時間で計算することは可能でしょうか？（これは、強い指数時間仮説が誤りである場合にのみ可能です。）
• X + Y のソートはo ( n ² log n )の時間で実行できますか？
• 行列乗算において最速のアルゴリズムは何ですか？
• すべてのペアの最短経路は、強いサブ3次時間、つまり、あるε > 0に対してO ( V ^3−ε )の時間で計算できますか？
• 多項式の恒等式判定に関するシュワルツ・ジッペル補題は、ランダム性を排除できるだろうか？
• 線形計画法は、強力な多項式時間アルゴリズムを許容するだろうか？（これは、スメールの問題リストの9番目の問題である。）
• 嫉妬のないケーキカットには、いくつのクエリが必要ですか？
• 最小全域木問題のアルゴリズム的複雑度はどのくらいですか？言い換えれば、MST問題の決定木複雑度はどのくらいですか？MSTを計算する最適なアルゴリズムは知られていますが、決定木に依存するため、その複雑度は不明です。
• ギルバート・ポラック予想：ユークリッド平面のシュタイナー比は${\displaystyle 2/{\sqrt {3}}}$？

• バレンデレヒト・ゲウバース・クロップ予想：弱正規化純粋型システムはすべて強正規化もするのか？

• 乗法指数線形論理は決定可能か？
• アーンデラー・カープ・ローゼンバーグ予想は正しいのか？
• チェルニー予想：決定性有限オートマトンが${\displaystyle n}$状態には同期ワードがあり、最大で長さが1つである必要があります${\displaystyle (n-1)^{2}}$？
• 一般化されたスター高さ問題：すべての正規言語は、クリーネスターのネスト深度が制限された一般化された正規表現を使用して表現できますか？
• 単語分離問題：長さの与えられた2つの文字列に対して異なる動作をする決定性有限オートマトンには、いくつの状態が必要か。${\displaystyle n}$？
• すべての固有の基本セルオートマトンにおけるチューリング完全性の状態はどうなっていますか？
• 最小不完全語の長さが${\displaystyle M}$は多項式である${\displaystyle l(M)}$あるいは、${\displaystyle sl(M)}$知られているように、${\displaystyle M}$すべての​${\displaystyle u_{1},...,u_{n},v_{1},...,v_{m}\in M}$、${\displaystyle u_{1}...u_{n}=v_{1}...v_{m}}$暗示する${\displaystyle n=m}$そして$u_i=v_i$すべての人々のために${\displaystyle 0<i\leq n}$このような場合、多項式による上限が存在するかどうかはまだ分かっていません。これは、レスティボ予想（一般には既に反証されているものの、上限は依然として不明）を弱める可能性のある要因です。
• すべての正の整数を決定する${\displaystyle n}$連結すると${\displaystyle n}$そして${\displaystyle n^{2}}$ベースで${\displaystyle b}$最大で${\displaystyle k}$固定の異なる文字${\displaystyle b}$そして${\displaystyle k}$。

• 物理学における未解決問題一覧
• 数学における未解決問題一覧

• Woeginger, Gerhard J. 「厳密アルゴリズムに関する未解決問題」離散応用数学156（2008）：397–405。
• RTA の未解決問題リスト–リライティングにおける未解決問題。
• TLCA 未解決問題リスト–型付きラムダ計算の分野における未解決問題。