NP中間体

計算複雑性において、複雑性クラス NPに属するが、クラスPにもNP 完全性にも属さない問題はNP 中間問題と呼ばれ、そのような問題のクラスはNPIと呼ばれます。1975年にRichard E. Ladnerによって示されたLadner の定理^[¹^]は、P ≠ NPならば NPI は空ではない、つまり NP には P にも NP 完全性にも属さない問題が含まれる、と主張する結果です。NPI 問題が存在するならば P ≠ NP であることも真であるため、P = NP であるのは NPI が空である場合のみであることがわかります。

P ≠ NP という仮定の下で、ラドナーは NPI の問題を明示的に構築しているが、この問題は人為的で、それ以外は面白くない。どのような「自然な」問題にも同じ性質があるかは未解決の問題である。シェーファーの二分法定理は、制約付きブール充足可能性問題のクラスが NPI に含まれない条件を提供する。^{[ 2 ]}^{[ 3 ]} NP 中間問題として有力な候補と考えられている問題には、グラフ同型問題、因数分解と離散対数の決定版などがある。

指数時間仮説の下では、双曲平面上の与えられた円盤の集合から大きな互いに素な単位円盤の集合を見つける問題^[⁴^]や、与えられたグラフの誘導部分グラフではない少数の頂点を持つグラフを見つける問題^[⁵^]など、準多項式時間を必要とする自然な問題が存在し、その時間内に解決できる。指数時間仮説はまた、準多項式時間の問題がNP完全であることはあり得ないことを意味しており、この仮定の下ではこれらの問題はNP中間でなければならない。

NP中間レベルである可能性のある問題のリスト

代数学と数論

整数の因数分解の決定版：入力に対して $n$ そして $k$ 、 $n$ 区間内に因子がある $[2,k]$ ？
離散対数問題の決定版、および暗号学的仮定に関連するその他の問題
線形除算性：与えられた整数 $x$ そして $y$ 、 $y$ 1を法とする約数を持つ $x$ ？^{[ 6 ]}^{[ 7 ]}

ブール論理

IMSATは、「交差する単調CNF」のブール充足可能性問題です。結合標準形とは、各節が正の項のみ、または負の項のみを含み、各正の節が各負の節と共通の変数を持つ形式です^{[ 8 ]。}
最小回路サイズ問題：ブール関数の真理値表と正の整数が与えられた場合 $s$ 最大でサイズの回路は存在するか $s$ この機能のために？^{[ 9 ]}
単調双対化：単調ブール関数のCNF式とDNF式が与えられた場合、それらは同じ関数を表しているか？^{[ 10 ]}
単調自己双対性：ブール関数のCNF式が与えられたとき、その関数は、すべての変数を否定し、さらに出力値を否定する変換の下で不変か？^{[ 10 ]}

計算幾何学と計算トポロジー

2 つの二分木間の回転距離^{[ 11 ]}または同じ凸多角形の 2 つの三角形分割間の反転距離が、所定の閾値以下であるかどうかを判定する。
距離多重集合から線上の点を再構築するターンパイク問題^{[ 12 ]}
一定数の物体の長さを持つ切断ストック問題^{[ 13 ]}
結び目の自明性^{[ 14 ]}
凸多面体上の単純な閉じた準測地線を見つける^{[ 15 ]}

ゲーム理論

パリティゲームでは、グラフの頂点は次のステップを選択するプレイヤーによってラベル付けされ、到達した最優先頂点のパリティによって勝者が決定されます^{[ 16 ]。}
確率的グラフゲームの勝者を決定する。このゲームでは、グラフの頂点は、次のステップを選択するプレイヤーによってラベル付けされるか、ランダムに選択されるかによってラベル付けされ、勝者は指定されたシンク頂点に到達することによって決定される。^{[ 17 ]}

グラフアルゴリズム

グラフ同型性問題^{[ 18 ]}
グラフの自己同型群を見つける^{[ 19 ]}
グラフの自己同型写像の数を求める^{[ 19 ]}
平面最小二等分法^{[ 20 ]}
グラフが優雅なラベル付けを許容するかどうかを決定する^{[ 21 ]}
葉のべき乗と $k$ 葉のべき乗の認識^{[ 22 ]}
クリーク幅が制限されたグラフの認識^{[ 23 ]}
固定エッジを持つ同時埋め込みの存在をテストする^{[ 24 ]}

その他

与えられた集合族のヴァプニク・チェルヴォネンキス次元が与えられた境界を下回っているかどうかをテストする^{[ 25 ]}

参考文献

↑ラドナー、リチャード (1975)。「多項式時間還元可能性の構造について」。ACMジャーナル。22 ( 1 ): 155–171。doi : 10.1145/321864.321877。S2CID 14352974。
↑ Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Marx, Maarten; Spencer, Joel ; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007).有限モデル理論とその応用. 理論計算機科学テキストシリーズ. EATCSシリーズ. ベルリン: Springer-Verlag . p. 348. ISBN 978-3-540-00428-8. Zbl 1133.03001 .
↑ Schaefer, Thomas J. (1978). "充足可能性問題の複雑性" (PDF) . Proc. 10th Ann. ACM Symp. on Theory of Computing . pp. 216–226 . MR 0521057 .
↑ Kisfaludi-Bak, Sándor (2020). "双曲交差グラフと（準）多項式時間". Chawla, Shuchi (編). Proceedings of the 31st Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. pp. 1621–1638 . arXiv : 1812.03960 . doi : 10.1137 /1.9781611975994.100 . ISBN 978-1-61197-599-4。
↑ Eppstein, David ; Lincoln, Andrea; Williams, Virginia Vassilevska (2023). "Quasipolynomiality of the smallest missing induced subgraph" . Journal of Graph Algorithms and Applications . 27 (5): 329– 339. arXiv : 2306.11185 . doi : 10.7155/jgaa.00625 .
↑ Adleman, Leonard; Manders, Kenneth (1977). "還元可能性、ランダム性、および扱いにくさ".第 9 回 ACM 理論計算機科学シンポジウム (STOC '77) 議事録。doi : 10.1145 /800105.803405。
↑パパディミトリウ、クリストス H. (1994).計算複雑性. アディソン・ウェスリー. p. 236. ISBN 9780201530827。
↑ Eiter, Thomas; Gottlob, Georg (2002). "ハイパーグラフ横断計算と論理およびAIにおける関連問題". Flesca, Sergio; Greco, Sergio; Leone, Nicola; Ianni, Giovambattista (編).人工知能における論理、欧州会議、JELIA 2002、イタリア、コセンツァ、9月23-26日、議事録. Lecture Notes in Computer Science. Vol. 2424. Springer. pp. 549–564 . doi : 10.1007/3-540-45757-7_53 . ISBN 978-3-540-44190-8。
↑ Kabanets, Valentine; Cai, Jin-Yi (2000). "回路最小化問題".第32回理論計算機科学シンポジウム論文集. 米国オレゴン州ポートランド. pp. 73–79 . doi : 10.1145/335305.335314 . ISBN 1-58113-184-4。S2CID 785205。ECCC TR99-045。
1 2 Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008). "単調双対化の計算的側面：簡単な概説" . Discrete Applied Mathematics . 156 (11): 2035–2049 . doi : 10.1016/j.dam.2007.04.017 . MR 2437000. S2CID 10096898 .
↑ Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "回転距離、三角形分割、双曲幾何学" . Journal of the American Mathematical Society . 1 (3): 647– 681. doi : 10.2307/1990951 . JSTOR 1990951 . MR 0928904 .
↑ Skiena, Steven; Smith, Warren D.; Lemke, Paul (1990). "点間距離からの集合の再構築（拡張要約）".In Seidel, Raimund (ed.). Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990. ACM. pp. 332–339 . doi : 10.1145/98524.98598 . ISBN 0-89791-362-0。
↑ Jansen, Klaus; Solis-Oba, Roberto (2011). "A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths". Mathematics of Operations Research . 36 (4): 743– 753. doi : 10.1287/moor.1110.0515 . MR 2855867 .
↑ Lackenby, Marc (2021). "The efficient certification of knottedness and Thurston norm" . Advances in Mathematics . 387 107796: Paper No. 107796. arXiv : 1604.00290 . doi : 10.1016/j.aim.2021.107796 . MR 4274879. S2CID 119307517 .
↑ Demaine, Erik D. ; O'Rourke, Joseph (2007). "24の測地線：リュステルニク-シュニレルマン".幾何学的折り畳みアルゴリズム：連結、折り紙、多面体. ケンブリッジ：ケンブリッジ大学出版局. pp. 372–375 . doi : 10.1017/CBO9780511735172 . ISBN 978-0-521-71522-5. MR 2354878 . 。
↑ Jurdziński, Marcin (1998). 「同点ゲームにおける勝者の決定はUPにある」 $\cap$ co-UP」。Information Processing Letters . 68 (3): 119– 124. doi : 10.1016/S0020-0190(98)00150-1 . MR 1657581 .
↑ Condon, Anne (1992). "確率ゲームの複雑性" . Information and Computation . 96 (2): 203– 224. doi : 10.1016/0890-5401(92)90048-K . MR 1147987 .
↑ Grohe, Martin; Neuen, Daniel (2021年6月)「グラフ同型問題に関する最近の進歩」『組合せ論概論2021』ケンブリッジ大学出版局、pp. 187–234。arXiv : 2011.01366 . doi : 10.1017 / 9781009036214.006 . ISBN 978-1-009-03621-4. S2CID 226237505 .
1 2 Mathon, R. (1979). "グラフ同型性計数問題に関する注記". Information Processing Letters . 8 (3): 131– 132. doi : 10.1016/0020-0190(79)90004-8 .
↑ Karpinski, Marek (2002). "最小二分問題の近似可能性：アルゴリズム上の課題". Diks, Krzysztof; Rytter, Wojciech (編). Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings . Lecture Notes in Computer Science. Vol. 2420. Springer. pp. 59–67 . doi : 10.1007/3-540-45687-2_4 . ISBN 978-3-540-44040-6。
↑ Gallian, Joseph A. (2021年12月17日). 「グラフラベル付けの動的調査」 . Electronic Journal of Combinatorics . 5 : Dynamic Survey 6. MR 1668059 .
↑ Nishimura, N.; Ragde, P.; Thilikos, DM (2002). "葉ラベル付き木のグラフパワーについて". Journal of Algorithms . 42 : 69– 108. doi : 10.1006/jagm.2001.1195 .。
↑ Fellows, Michael R. ; Rosamond, Frances A. ; Rotics, Udi; Szeider, Stefan (2009). "Clique-width is NP-complete". SIAM Journal on Discrete Mathematics . 23 (2): 909– 939. doi : 10.1137/070687256 . MR 2519936 . 。
↑ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006). "固定エッジによる同時グラフ埋め込み". Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers (PDF) . Lecture Notes in Computer Science. Vol. 4271. Berlin: Springer. pp. 325–335 . doi : 10.1007/11917496_29 . ISBN 978-3-540-48381-6. MR 2290741 . 2021-10-22 にオリジナル(PDF)からアーカイブされました。2019-09-10 に取得。。
↑ Papadimitriou, Christos H. ; Yannakakis, Mihalis (1996). "On limited nondeterminism and the complexity of the VC dimension" . Journal of Computer and System Sciences . 53 (2, part 1): 161– 170. doi : 10.1006/jcss.1996.0058 . MR 1418886 .

外部リンク

複雑性動物園：クラスNPI
基本構造、チューリング還元可能性、NP困難性
ランス・フォートナウ（2003年3月24日）。「複雑性の基礎、レッスン16：ラドナーの定理」。 2013年11月1日取得。

[1] ラドナー、リチャード (1975)。「多項式時間還元可能性の構造について」。ACMジャーナル。22 ( 1 ): 155–171。doi : 10.1145/321864.321877。S2CID 14352974。

[2] Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Marx, Maarten; Spencer, Joel ; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007).有限モデル理論とその応用. 理論計算機科学テキストシリーズ. EATCSシリーズ. ベルリン: Springer-Verlag . p. 348. ISBN 978-3-540-00428-8. Zbl 1133.03001 .

[3] Schaefer, Thomas J. (1978). "充足可能性問題の複雑性" (PDF) . Proc. 10th Ann. ACM Symp. on Theory of Computing . pp. 216–226 . MR 0521057 .

[4] Kisfaludi-Bak, Sándor (2020). "双曲交差グラフと（準）多項式時間". Chawla, Shuchi (編). Proceedings of the 31st Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. pp. 1621–1638 . arXiv : 1812.03960 . doi : 10.1137 /1.9781611975994.100 . ISBN 978-1-61197-599-4。

[5] Eppstein, David ; Lincoln, Andrea; Williams, Virginia Vassilevska (2023). "Quasipolynomiality of the smallest missing induced subgraph" . Journal of Graph Algorithms and Applications . 27 (5): 329– 339. arXiv : 2306.11185 . doi : 10.7155/jgaa.00625 .

[6] Adleman, Leonard; Manders, Kenneth (1977). "還元可能性、ランダム性、および扱いにくさ".第 9 回 ACM 理論計算機科学シンポジウム (STOC '77) 議事録。doi : 10.1145 /800105.803405。

[7] パパディミトリウ、クリストス H. (1994).計算複雑性. アディソン・ウェスリー. p. 236. ISBN 9780201530827。

[8] Eiter, Thomas; Gottlob, Georg (2002). "ハイパーグラフ横断計算と論理およびAIにおける関連問題". Flesca, Sergio; Greco, Sergio; Leone, Nicola; Ianni, Giovambattista (編).人工知能における論理、欧州会議、JELIA 2002、イタリア、コセンツァ、9月23-26日、議事録. Lecture Notes in Computer Science. Vol. 2424. Springer. pp. 549–564 . doi : 10.1007/3-540-45757-7_53 . ISBN 978-3-540-44190-8。

[9] Kabanets, Valentine; Cai, Jin-Yi (2000). "回路最小化問題".第32回理論計算機科学シンポジウム論文集. 米国オレゴン州ポートランド. pp. 73–79 . doi : 10.1145/335305.335314 . ISBN 1-58113-184-4。S2CID 785205。ECCC TR99-045。

[emg-10] 1 2 Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008). "単調双対化の計算的側面：簡単な概説" . Discrete Applied Mathematics . 156 (11): 2035–2049 . doi : 10.1016/j.dam.2007.04.017 . MR 2437000. S2CID 10096898 .

[11] Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "回転距離、三角形分割、双曲幾何学" . Journal of the American Mathematical Society . 1 (3): 647– 681. doi : 10.2307/1990951 . JSTOR 1990951 . MR 0928904 .

[12] Skiena, Steven; Smith, Warren D.; Lemke, Paul (1990). "点間距離からの集合の再構築（拡張要約）".In Seidel, Raimund (ed.). Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990. ACM. pp. 332–339 . doi : 10.1145/98524.98598 . ISBN 0-89791-362-0。

[13] Jansen, Klaus; Solis-Oba, Roberto (2011). "A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths". Mathematics of Operations Research . 36 (4): 743– 753. doi : 10.1287/moor.1110.0515 . MR 2855867 .

[14] Lackenby, Marc (2021). "The efficient certification of knottedness and Thurston norm" . Advances in Mathematics . 387 107796: Paper No. 107796. arXiv : 1604.00290 . doi : 10.1016/j.aim.2021.107796 . MR 4274879. S2CID 119307517 .

[15] Demaine, Erik D. ; O'Rourke, Joseph (2007). "24の測地線：リュステルニク-シュニレルマン".幾何学的折り畳みアルゴリズム：連結、折り紙、多面体. ケンブリッジ：ケンブリッジ大学出版局. pp. 372–375 . doi : 10.1017/CBO9780511735172 . ISBN 978-0-521-71522-5. MR 2354878 . 。

[16] Jurdziński, Marcin (1998). 「同点ゲームにおける勝者の決定はUPにある」 $\cap$ co-UP」。Information Processing Letters . 68 (3): 119– 124. doi : 10.1016/S0020-0190(98)00150-1 . MR 1657581 .

[17] Condon, Anne (1992). "確率ゲームの複雑性" . Information and Computation . 96 (2): 203– 224. doi : 10.1016/0890-5401(92)90048-K . MR 1147987 .

[18] Grohe, Martin; Neuen, Daniel (2021年6月)「グラフ同型問題に関する最近の進歩」『組合せ論概論2021』ケンブリッジ大学出版局、pp. 187–234。arXiv : 2011.01366 . doi : 10.1017 / 9781009036214.006 . ISBN 978-1-009-03621-4. S2CID 226237505 .

[mathon-19] 1 2 Mathon, R. (1979). "グラフ同型性計数問題に関する注記". Information Processing Letters . 8 (3): 131– 132. doi : 10.1016/0020-0190(79)90004-8 .

[20] Karpinski, Marek (2002). "最小二分問題の近似可能性：アルゴリズム上の課題". Diks, Krzysztof; Rytter, Wojciech (編). Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings . Lecture Notes in Computer Science. Vol. 2420. Springer. pp. 59–67 . doi : 10.1007/3-540-45687-2_4 . ISBN 978-3-540-44040-6。

[21] Gallian, Joseph A. (2021年12月17日). 「グラフラベル付けの動的調査」 . Electronic Journal of Combinatorics . 5 : Dynamic Survey 6. MR 1668059 .

[22] Nishimura, N.; Ragde, P.; Thilikos, DM (2002). "葉ラベル付き木のグラフパワーについて". Journal of Algorithms . 42 : 69– 108. doi : 10.1006/jagm.2001.1195 .。

[23] Fellows, Michael R. ; Rosamond, Frances A. ; Rotics, Udi; Szeider, Stefan (2009). "Clique-width is NP-complete". SIAM Journal on Discrete Mathematics . 23 (2): 909– 939. doi : 10.1137/070687256 . MR 2519936 . 。

[24] Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006). "固定エッジによる同時グラフ埋め込み". Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers (PDF) . Lecture Notes in Computer Science. Vol. 4271. Berlin: Springer. pp. 325–335 . doi : 10.1007/11917496_29 . ISBN 978-3-540-48381-6. MR 2290741 . 2021-10-22 にオリジナル(PDF)からアーカイブされました。2019-09-10 に取得。。

[25] Papadimitriou, Christos H. ; Yannakakis, Mihalis (1996). "On limited nondeterminism and the complexity of the VC dimension" . Journal of Computer and System Sciences . 53 (2, part 1): 161– 170. doi : 10.1006/jcss.1996.0058 . MR 1418886 .

[

[ 2 ]

[ 3 ]

[

[

[ 6 ]

[ 7 ]

[ 8 ]。

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]。

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]