Loading article…
理論計算機科学 では、関数が 準多項式増加を示すとは、ビッグオー記法を用いて表現される 定数 に対しての形式の 上限を持つ場合を言う。つまり、多項式関数の指数関数によって制限される。これは、多項式と多項式増加の関数を一般化し、 を取ることができる。準多項式増加を持つ関数は、準多項式的に制限されているとも言われる。[1]
準多項式増加は、計算複雑度が多項式ではないが指数関数よりも大幅に小さい特定のアルゴリズムを説明するために、アルゴリズムの分析で使用されてきました。特に、最悪の実行時間が準多項式増加を示すアルゴリズムは、準多項式時間かかると言われています。[2]時間複雑度だけでなく、一部のアルゴリズムは、準多項式の空間複雑度を必要とし、[3]準多項式の数の並列プロセッサを使用し、[4]準多項式サイズの代数式として表すことができ[2]、準多項式競合比 を持ちます。[5]他の場合には、準多項式増加は、問題への入力に対する制約をモデル化するために使用され、存在する場合、それらの入力に対するアルゴリズムから良好なパフォーマンスが得られます。[1]また、一部の問題では出力のサイズを制限することもできます。例えば、線形に変化する辺の重みを持つ最短経路問題の場合、異なる解の数は準多項式になることがある。[6] [7]
理論計算機科学の枠を超えて、準多項式成長境界は数学でも使用されており、例えば多面体組合せ論における多面体の直径に関するヒルシュ予想の部分的な結果や[8] 、特定のグラフのクラスにおけるクリークと独立集合のサイズの関係などである。[9]しかし、多面体組合せ論と列挙組合せ論では、同じ単語の異なる意味も使用され、準多項式、つまり周期係数を持つことによって多項式を一般化する関数を指す。[10]
参考文献
- ^ ab Ackermann, Heiner; Newman, Alantha; Röglin, Heiko; Vöcking, Berthold (2007)、「近似および平滑化されたパレート曲線に基づく意思決定」、理論計算機科学、378 (3): 253–270、doi : 10.1016/j.tcs.2007.02.034、MR 2325290
- ^ ab von zur Gathen, Joachim (1987)、「実行可能な算術計算: Valiant の仮説」、Journal of Symbolic Computation、4 (2): 137–172、doi :10.1016/S0747-7171(87)80063-9、MR 0922386
- ^ Fearnley, John; Jain, Sanjay; de Keijzer, Bart; Schewe, Sven; Stephan, Frank; Wojtczak, Dominik (2019)、「準多項式時間と準線形空間でパリティゲームを解くための順序付けられたアプローチ」、International Journal on Software Tools for Technology Transfer、21 (3): 325–349、arXiv : 1703.01296、doi :10.1007/S10009-019-00509-3
- ^ フェナー、スティーブン; グルジャー、ロヒット; ティエラウフ、トーマス (2021)、「二部完全マッチングは準NCである」、SIAM Journal on Computing、50 (3): 218–235、arXiv : 1601.06319、doi :10.1137/16M1097870、MR 4277935
- ^ Bosek, Bartlomiej; Krawczyk, Tomasz (2010)、「オンライン チェーン パーティショニングの指数関数以下の上限」、第 51 回 IEEE コンピュータ サイエンスの基礎に関するシンポジウム、FOCS 2010、2010 年 10 月 23 ～ 26 日、米国ネバダ州ラスベガス、 IEEE コンピュータ ソサエティ、pp. 347 ～ 354、doi :10.1109/FOCS.2010.40、ISBN 978-1-4244-8525-3
- ^ カーステンセン、パトリシア・ジューン（1983）、パラメトリック線形計画法と組合せ計画法におけるいくつかの問題の複雑性、博士論文、ミシガン大学、ProQuest 303275648
- ^ フロリアン、バース;フンケ、ステファン。 Proissl、Claudius (2022)、「任意の次元における極端な最短経路の数の上限」、Chechik、Shiri にて。ナバロ、ゴンサロ。ローテンベルク、エヴァ。 Herman、Grzegorz (編)、第 30 回アルゴリズムに関する欧州年次シンポジウム、ESA 2022、2022 年 9 月 5 ～ 9 日、ベルリン/ポツダム、ドイツ、LIPIcs、vol. 244、Schloss Dagstuhl - Leibniz-Zentrum für Informatik、pp. 14:1–14:12、doi : 10.4230/LIPICS.ESA.2022.14
- ^ カライ、ギル; クライトマン、ダニエル J. (1992)、「多面体グラフの直径に対する準多項式境界」、アメリカ数学会報、新シリーズ、26 (2): 315–316、doi : 10.1090/S0273-0979-1992-00285-9、MR 1130448
- ^ Pilipczuk, Marek; Sokołowski, Michał (2023)、「制限付きツイン幅のグラフは準多項式的に制限される」、Journal of Combinatorial Theory、シリーズ B、161 : 382–406、arXiv : 2202.07608、doi :10.1016/j.jctb.2023.02.006、MR 4568111
- ^ McAllister, Tyrrell B.; Woods, Kevin M. (2005)、「有理多面体の Ehrhart 準多項式の最小周期」、Journal of Combinatorial Theory、Series A、109 (2): 345–352、arXiv : math/0310255、doi : 10.1016/j.jcta.2004.08.006、MR 2121031
