■コンピュータ・サイエンスとは何か

コンピュータ・サイエンスで取り組まれている問題の一覧を紹介しよう。

計算複雑性

• P対NP問題
• BQPとNPの関係は？
• NC = P問題
• NP = co-NP問題
• P = BPP問題
• P = PSPACE問題
• L = NL問題
• 多項式階層 = PSPACE問題
• L = P問題
• L = RL問題
• ユニークゲーム予想
• 指数時間仮説は真か？強い指数時間仮説（SETH）は真か？
• 一方向関数は存在するか？公開鍵暗号は可能か？
• 対数ランク予想

特定のアルゴリズム問題における多項式時間と非決定性多項式時間

• 整数因数分解は古典（非量子）コンピュータで多項式時間で行えるか？
• 離散対数は古典（非量子）コンピュータで多項式時間で計算できるか？
• 格子の最短ベクトルは古典または量子コンピュータで多項式時間で計算できるか？
• グラフ同型問題は多項式時間で解けるか？
• グラフの正規化はグラフ同型問題と多項式時間で等価か？
• リーフパワーおよびk-リーフパワーは多項式時間で認識できるか？
• パリティゲームは多項式時間で解けるか？
• 二分木間の回転距離は多項式時間で計算できるか？
• 有界クリーク幅のグラフは多項式時間で認識できるか？
• 凸多面体上の単純閉準測地線を多項式時間で見つけることができるか？
• 与えられた2つのグラフに対して固定された辺を持つ同時埋め込みを多項式時間で見つけることができるか？
• 平方根和問題はチューリングマシンモデルで多項式時間で解けるか？

その他のアルゴリズム問題

• スプレーツリーの動的最適性予想：スプレーツリーは有界な競争比を持つか？
• 深さ優先探索木はNCで構築できるか？
• 高速フーリエ変換はo(n log n)時間で計算できるか？
• 2つのn桁の数の乗算の最速のアルゴリズムは何か？
• 決定論的で固定されたギャップシーケンスを持つシェルソートの平均ケース時間計算量の下限は何か？
• 3SUMは強い二次未満の時間、つまりO(n^{2−ϵ})時間で解けるか？
• 2つの文字列間の編集距離は強い二次未満の時間で計算できるか？（これは強い指数時間仮説が偽である場合にのみ可能）
• X + Yソートはo(n^2 log n)時間で行えるか？
• 行列乗算の最速のアルゴリズムは何か？
• 全対間最短経路は強い三次未満の時間、つまりO(V^{3−ϵ})時間で計算できるか？
• 多項式同一性テストのためのシュワルツ・ジッペル補題は非乱択化できるか？
• 線形計画法は強い多項式時間アルゴリズムを持つか？（これはスマイルの問題リストの問題#9）
• 嫉妬のないケーキカットに必要なクエリ数は何か？
• 最小全域木問題のアルゴリズム的複雑性は何か？同様に、MST問題の決定木複雑性は何か？MSTを計算するための最適なアルゴリズムは知られているが、決定木に依存しているため、その複雑性は不明。
• ギルバート・ポラック予想：ユークリッド平面のシュタイナー比は2/√3か？

プログラミング言語理論

• POPLmark
• バレンドレヒト・ギューヴァース・クロップ予想

その他の問題

• アンデラ・カープ・ローゼンバーグ予想は真か？
• チェルニー予想：n状態の決定性有限オートマトンが同期語を持つ場合、その長さは最大で(n-1)^2か？
• 一般化されたスター高さ問題：すべての正則言語は、限定されたネスト深さのクリーン星を持つ一般化された正則表現を使用して表現できるか？
• 単語の分離問題：2つの与えられた長さnの文字列に対して異なる動作をする決定性有限オートマトンに必要な状態数は何か？
• すべてのユニークな基本セルオートマトンのチューリング完全性の状態は何か？

Permalink | 記事への反応(0) | 15:26

ツイートシェア