問いの一覧
どの問いも、複数のアプローチとその判定者とともに記録されています。解決したかどうかはアプローチごとに決まります。
人類審査を通過した問いです。アプローチが2つ以上あり、それぞれに判定者と差分が書かれています。
8 件
- P と NP は等しいか？（P vs NP 問題）
アプローチ 4 件 · 未着手 / 進行中 / この道では到達できないと証明済み
- NP と coNP は等しいか？（短い反証は常に存在するか）
アプローチ 3 件 · 未着手 / 進行中
- 一方向性関数は存在するか？
アプローチ 2 件 · 進行中 / この道では到達できないと証明済み
- 確率的多項式時間アルゴリズムは、すべて決定的に置き換えられるか？（P = BPP か）
アプローチ 2 件 · 進行中
- NEXP は多項式サイズの回路を持つか？
アプローチ 2 件 · 進行中 / この道では到達できないと証明済み
- 強指数時間仮説（SETH）は正しいか？
アプローチ 2 件 · 進行中 / この道では到達できないと証明済み
computer-sciencecomputational-complexityfine-grained-complexity
- ユニークゲーム予想は正しいか？
アプローチ 2 件 · 進行中
- グラフ同型判定は多項式時間で解けるか？
アプローチ 3 件 · 進行中 / この道では到達できないと証明済み