NP中間体

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

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

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

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

代数学と数論

整数の因数分解の決定バージョン: およびを入力とすると、区間に因数がありますか? $n$ $k$ $n$ $[2,k]$
離散対数問題および暗号仮定に関連するその他の問題の決定バージョン
線形割り切れる可能性: 整数とが与えられたとき、を法として 1 と合同な約数を持つか? ^[6]^[7] $x$ $y$ $y$ $x$

ブール論理

IMSAT、「交差単調CNF」のブール充足問題：連言正規形、各節は正または負の項のみを含み、各正の節は各負の節と共通の変数を持つ^[8]
最小回路サイズ問題：ブール関数の真理値表と正の整数が与えられたとき、この関数に対して最大でサイズの回路は存在するか？ ^[9] $s$ $s$
単調双対化：単調ブール関数の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.ZBL1133.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 (編)。第31回ACM-SIAM離散アルゴリズムシンポジウムの議事録、SODA 2020、ソルトレイクシティ、ユタ州、米国、2020年1月5～8日。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). 「最小の欠落誘導サブグラフの準多項式」. Journal of Graph Algorithms and Applications . 27 (5): 329–339. arXiv : 2306.11185 . doi : 10.7155/jgaa.00625 .
^ Adleman, Leonard; Manders, Kenneth (1977). 「Reducibility, randomness, and intractibility」. Proceedings of the 9th ACM Symp. on Theory of Computing (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 (編)。Logics in Artificial Intelligence、ヨーロッパ会議、JELIA 2002、コゼンツァ、イタリア、9 月、23-26 日、議事録。Lecture Notes in Computer Science。Vol . 2424。Springer。pp. 549–564。doi :10.1007/3-540-45757-7_53。
^ Kabanets, Valentine; Cai, Jin- Yi (2000) . 「回路最小化問題」。Proc . 32nd Symposium on Theory of Computing。ポートランド、オレゴン、米国。pp. 73–79。doi : 10.1145/335305.335314。S2CID 785205。ECCC TR99-045。
^ ab Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008). 「単調双対化の計算的側面: 簡単な調査」.離散応用数学. 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). 「回転距離、三角形分割、双曲幾何学」.アメリカ数学会誌. 1 (3): 647–681. doi : 10.2307/1990951 . JSTOR 1990951. MR 0928904.
^ Skiena, Steven; Smith, Warren D.; Lemke, Paul (1990). 「Reconstructing Sets from Interpoint Distances (Extended Abstract)」。Seidel, Raimund (ed.) 著。米国カリフォルニア州バークレーで開催された第 6 回計算幾何学シンポジウムの議事録。ACM。pp. 332–339。doi : 10.1145/98524.98598。
^ Jansen, Klaus; Solis-Oba, Roberto (2011). 「オブジェクトの長さが一定であるカッティングストック問題に対する多項式時間 OPT + 1 アルゴリズム」.オペレーションズリサーチの数学. 36 (4): 743–753. doi :10.1287/moor.1110.0515. MR 2855867.
^ Lackenby, Marc (2021). 「結び目性とサーストンノルムの効率的な証明」. Advances in Mathematics . 387 : 論文番号107796. arXiv : 1604.00290 . doi : 10.1016/j.aim.2021.107796 . MR 4274879. S2CID 119307517.
^ Demaine, Erik D. ; O'Rourke, Joseph ( 2007). 「24 Geodesics: Lyusternik–Schnirelmann」.幾何学的折り畳みアルゴリズム: リンク、折り紙、多面体。ケンブリッジ: ケンブリッジ大学出版局。pp. 372–375。doi :10.1017/ CBO9780511735172。ISBN 978-0-521-71522-5MR 2354878 。。
^ Jurdziński, Marcin (1998). 「パリティゲームの勝者を決めるのはUP co-UPである」. Information Processing Letters . 68 (3): 119–124. doi :10.1016/S0020-0190(98)00150-1. MR 1657581. $\cap$
^ Condon, Anne (1992). 「確率的ゲームの複雑性」.情報と計算. 96 (2): 203–224. doi : 10.1016/0890-5401(92)90048-K . MR 1147987.
^ Grohe, Martin; Neuen, Daniel (2021年6月). 「グラフ同型性問題に関する最近の進歩」. Surveys in Combinatorics 2021 . Cambridge University Press. pp. 187–234. arXiv : 2011.01366 . doi :10.1017/9781009036214.006. S2CID 226237505.
^ ab 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 (編)。コンピュータサイエンスの数学的基礎 2002、第 27 回国際シンポジウム、MFCS 2002、ワルシャワ、ポーランド、2002 年 8 月 26 ～ 30 日、議事録。コンピュータサイエンスの講義ノート。第 2420 巻。Springer。pp. 59 ～ 67。doi : 10.1007/3-540-45687-2_4。
^ 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. MR 2290741.。
^ Papadimitriou, Christos H. ; Yannakakis, Mihalis (1996). 「限定された非決定性と VC 次元の複雑さについて」. 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.ZBL1133.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 (編)。第31回ACM-SIAM離散アルゴリズムシンポジウムの議事録、SODA 2020、ソルトレイクシティ、ユタ州、米国、2020年1月5～8日。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). 「最小の欠落誘導サブグラフの準多項式」. Journal of Graph Algorithms and Applications . 27 (5): 329–339. arXiv : 2306.11185 . doi : 10.7155/jgaa.00625 .

[6] Adleman, Leonard; Manders, Kenneth (1977). 「Reducibility, randomness, and intractibility」. Proceedings of the 9th ACM Symp. on Theory of Computing (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 (編)。Logics in Artificial Intelligence、ヨーロッパ会議、JELIA 2002、コゼンツァ、イタリア、9 月、23-26 日、議事録。Lecture Notes in Computer Science。Vol . 2424。Springer。pp. 549–564。doi :10.1007/3-540-45757-7_53。

[9] ^ Kabanets, Valentine; Cai, Jin- Yi (2000) . 「回路最小化問題」。Proc . 32nd Symposium on Theory of Computing。ポートランド、オレゴン、米国。pp. 73–79。doi : 10.1145/335305.335314。S2CID 785205。ECCC TR99-045。

[emg-10] Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008). 「単調双対化の計算的側面: 簡単な調査」.離散応用数学. 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). 「回転距離、三角形分割、双曲幾何学」.アメリカ数学会誌. 1 (3): 647–681. doi : 10.2307/1990951 . JSTOR 1990951. MR 0928904.

[12] Skiena, Steven; Smith, Warren D.; Lemke, Paul (1990). 「Reconstructing Sets from Interpoint Distances (Extended Abstract)」。Seidel, Raimund (ed.) 著。米国カリフォルニア州バークレーで開催された第 6 回計算幾何学シンポジウムの議事録。ACM。pp. 332–339。doi : 10.1145/98524.98598。

[13] Jansen, Klaus; Solis-Oba, Roberto (2011). 「オブジェクトの長さが一定であるカッティングストック問題に対する多項式時間 OPT + 1 アルゴリズム」.オペレーションズリサーチの数学. 36 (4): 743–753. doi :10.1287/moor.1110.0515. MR 2855867.

[14] Lackenby, Marc (2021). 「結び目性とサーストンノルムの効率的な証明」. Advances in Mathematics . 387 : 論文番号107796. arXiv : 1604.00290 . doi : 10.1016/j.aim.2021.107796 . MR 4274879. S2CID 119307517.

[15] Demaine, Erik D. ; O'Rourke, Joseph ( 2007). 「24 Geodesics: Lyusternik–Schnirelmann」.幾何学的折り畳みアルゴリズム: リンク、折り紙、多面体。ケンブリッジ: ケンブリッジ大学出版局。pp. 372–375。doi :10.1017/ CBO9780511735172。ISBN 978-0-521-71522-5MR 2354878 。。

[16] Jurdziński, Marcin (1998). 「パリティゲームの勝者を決めるのはUP co-UPである」. Information Processing Letters . 68 (3): 119–124. doi :10.1016/S0020-0190(98)00150-1. MR 1657581. $\cap$

[17] Condon, Anne (1992). 「確率的ゲームの複雑性」.情報と計算. 96 (2): 203–224. doi : 10.1016/0890-5401(92)90048-K . MR 1147987.

[18] Grohe, Martin; Neuen, Daniel (2021年6月). 「グラフ同型性問題に関する最近の進歩」. Surveys in Combinatorics 2021 . Cambridge University Press. pp. 187–234. arXiv : 2011.01366 . doi :10.1017/9781009036214.006. S2CID 226237505.

[mathon-19] 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 (編)。コンピュータサイエンスの数学的基礎 2002、第 27 回国際シンポジウム、MFCS 2002、ワルシャワ、ポーランド、2002 年 8 月 26 ～ 30 日、議事録。コンピュータサイエンスの講義ノート。第 2420 巻。Springer。pp. 59 ～ 67。doi : 10.1007/3-540-45687-2_4。

[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. MR 2290741.。

[25] Papadimitriou, Christos H. ; Yannakakis, Mihalis (1996). 「限定された非決定性と VC 次元の複雑さについて」. Journal of Computer and System Sciences . 53 (2, part 1): 161–170. doi : 10.1006/jcss.1996.0058 . MR 1418886.