複雑性クラス
Latest Author
yuki2006
/Date 2015-07-06 17:02:28 / Views 8521
(追記歓迎！）
情報工学生やアルゴリズマーなら知っておいた良い知識だと思いますが、
競技プログラミングをする上では、深く知らなくても良いと思ってます。(*)
厳密な定義は、教科書やWikipediaに譲るとして、ゆるふわにわかった気にさせるページです。
(*)結局問題のクラスはPでも、 NP-Hardでも、EXPTIMEでも、計算時間的に解ける問題しか出ず.
計算量の見積りのほうが大事だと思うからです。（運営者の考えです。）
回答が、多項式時間で判定可能な問題のことである。
「決定性チューリングマシンが多項式時間で回答できる」というのが定義だが、詳しくは各自で。
yukicoderの問題でいうと以下の問題等がイメージしやすいかも 最適化(答えの最小化・最大化)問題に対しては、「答えがk以下(以上)か？」という質問に変換することで判定問題にできる。 その判定ができれば2分探索によって実際の答えを(十分な精度まで)多項式時間で求められることに注意する。
このようにしてできた対応する判定問題があるクラスに含まれるとき、(厳密ではないが)元の問題に対してそのクラスに含まれるということがある。
(対応する判定問題が)Pに含まれる最適化問題の例としては、 （なお、値を求めさせる問題はクラスFPというらしく、競技プログラミングの問題の多くはこれだと思われる）
ただ、これはクラスPに限らないが、判定問題でなく値を求めさせる問題であっても、自然な対応する定義のクラスを指してカジュアルに「そのクラスに含まれる」ということは多い。
（回答については述べてないことに注意）
競技プログラミングっぽくというと、スペシャルジャッジの判定が多項式時間で終わること。
実際の定義は
「非決定性チューリングマシンが多項式時間で回答できる」もしくは
「yesだったときの証拠が多項式時間で検証可能」
よくある誤りは「指数時間かかるからNP」、「PじゃないからNP」など。
（「NP完全」のこと指して、「NP」と言ってる事が多い？）
「クラスP」の問題はすべて「クラスNP」でもあります。
例え回答に指数時間以上かかっても、「証拠が多項式時間で検証できればNP」です。
$P \subseteq NP$ の関係がある (もし $P \neq NP$が証明されれば$P \subset NP$ である。現在この見方が強い)
yukicoderの問題でいうと以下の問題がイメージしやすいかも
NP完全の問題が多項式時間で解けてしまうと、P=NPということになる。(未だに証明されていない)
（つまり、NP完全の問題は多項式時間で解けないと思われる。）
正直、困難という名称がついてるが、困難っぽくはない気がしてます。
NPに入るがNP困難でもPでもない問題をNP-intermediate問題といい、いくつかの自然な問題がこれに属すると思われている（ex.グラフ同型)。
「NP」かつ「NP困難」は「NP完全」である。
多項式時間で実行される非決定性チューリングマシンが受理する実行パス(非決定性)の数が答えとなるようなもの。
いわば、クラスNPの数え上げ版。
「数え上げ」というが、確率問題や期待値問題もある意味での「数え上げ」とみなすことができるので、このクラスに入りうる。
競技プログラミングにおいては、ある数kで割った余りを答えさせることが多い。その場合、ModkPと呼ばれる問題クラスになる。
ただ、任意の素数modで割った余りを求められる場合には中国人剰余定理によって多項式時間で元の答えを得ることができるので、ある意味で同じことである。
判定問題が多項式時間で解ける問題でも、数え上げバージョンは#P完全となることがよくある。2部マッチング, 2SAT, トポロジカルソート などが例である。
たとえば、素数判定問題はMiller-Rabin法によりco-RPに含まれることがわかる(最近になって、AKSアルゴリズムによってPに含まれることが示された)。
(筆者の感覚的には)数論アルゴリズムやそれを応用したアルゴリズムに多い。たとえば、有限体上の多項式の因数分解にはzero-sided errorの期待多項式時間アルゴリズムがよく知られている。
複雑性クラス
いわゆるPとかNPのやつです。情報工学生やアルゴリズマーなら知っておいた良い知識だと思いますが、
競技プログラミングをする上では、深く知らなくても良いと思ってます。(*)
厳密な定義は、教科書やWikipediaに譲るとして、ゆるふわにわかった気にさせるページです。
(*)結局問題のクラスはPでも、 NP-Hardでも、EXPTIMEでも、計算時間的に解ける問題しか出ず.
計算量の見積りのほうが大事だと思うからです。（運営者の考えです。）
クラス P
判定問題(yes/no・possible/impossibleなど、どちらかを答えさせる問題）で、回答が、多項式時間で判定可能な問題のことである。
「決定性チューリングマシンが多項式時間で回答できる」というのが定義だが、詳しくは各自で。
yukicoderの問題でいうと以下の問題等がイメージしやすいかも 最適化(答えの最小化・最大化)問題に対しては、「答えがk以下(以上)か？」という質問に変換することで判定問題にできる。 その判定ができれば2分探索によって実際の答えを(十分な精度まで)多項式時間で求められることに注意する。
このようにしてできた対応する判定問題があるクラスに含まれるとき、(厳密ではないが)元の問題に対してそのクラスに含まれるということがある。
(対応する判定問題が)Pに含まれる最適化問題の例としては、 （なお、値を求めさせる問題はクラスFPというらしく、競技プログラミングの問題の多くはこれだと思われる）
ただ、これはクラスPに限らないが、判定問題でなく値を求めさせる問題であっても、自然な対応する定義のクラスを指してカジュアルに「そのクラスに含まれる」ということは多い。
クラス NP
判定問題で、証拠が多項式時間で検証可能な問題のことである。（回答については述べてないことに注意）
競技プログラミングっぽくというと、スペシャルジャッジの判定が多項式時間で終わること。
実際の定義は
「非決定性チューリングマシンが多項式時間で回答できる」もしくは
「yesだったときの証拠が多項式時間で検証可能」
よくある誤りは「指数時間かかるからNP」、「PじゃないからNP」など。
（「NP完全」のこと指して、「NP」と言ってる事が多い？）
「クラスP」の問題はすべて「クラスNP」でもあります。
例え回答に指数時間以上かかっても、「証拠が多項式時間で検証できればNP」です。
$P \subseteq NP$ の関係がある (もし $P \neq NP$が証明されれば$P \subset NP$ である。現在この見方が強い)
yukicoderの問題でいうと以下の問題がイメージしやすいかも
クラス NP完全 (NP-complete)
「クラス NP」の中で一番難しい問題クラスNP完全の問題が多項式時間で解けてしまうと、P=NPということになる。(未だに証明されていない)
（つまり、NP完全の問題は多項式時間で解けないと思われる。）
クラス NP困難 (NP-hard)
NPと同等以上（NPも含む）難しいだろうと思われるクラス。 つまり、「yesだったときの証拠が多項式時間"以上"で検証可能」や、判定問題ではないものもNP困難に含まれる。正直、困難という名称がついてるが、困難っぽくはない気がしてます。
NPに入るがNP困難でもPでもない問題をNP-intermediate問題といい、いくつかの自然な問題がこれに属すると思われている（ex.グラフ同型)。
「NP」かつ「NP困難」は「NP完全」である。
クラス #P (sharp-P)
数え上げ問題のクラス。多項式時間で実行される非決定性チューリングマシンが受理する実行パス(非決定性)の数が答えとなるようなもの。
いわば、クラスNPの数え上げ版。
「数え上げ」というが、確率問題や期待値問題もある意味での「数え上げ」とみなすことができるので、このクラスに入りうる。
競技プログラミングにおいては、ある数kで割った余りを答えさせることが多い。その場合、ModkPと呼ばれる問題クラスになる。
ただ、任意の素数modで割った余りを求められる場合には中国人剰余定理によって多項式時間で元の答えを得ることができるので、ある意味で同じことである。
#P完全 (#P-complete)
#Pの中で一番難しい問題のクラス。判定問題が多項式時間で解ける問題でも、数え上げバージョンは#P完全となることがよくある。2部マッチング, 2SAT, トポロジカルソート などが例である。
クラス BPP
乱数を使って多項式時間で定数確率で正しい答えが出せるような判定問題のクラス。「モンテカルロ法」(の中で多項式時間で実行されるもの)。クラス RP, co-RP
クラスBPPが両側誤りを許すのに対して、片側誤りしか許さないクラス。片側誤りの方向に対応してRPとco-RPがある。たとえば、素数判定問題はMiller-Rabin法によりco-RPに含まれることがわかる(最近になって、AKSアルゴリズムによってPに含まれることが示された)。
クラス ZPP
乱数を使って期待多項式時間で解ける判定問題のクラス。「ラスベガス法」(の中で期待多項式時間で実行されるもの)。 RPが片側誤りを許すのに対して"zero-sided error"であり、停止したら絶対に正しい答えを返す。(筆者の感覚的には)数論アルゴリズムやそれを応用したアルゴリズムに多い。たとえば、有限体上の多項式の因数分解にはzero-sided errorの期待多項式時間アルゴリズムがよく知られている。
xx-hard, xx-complete のクラスについて
クラスCに対する"C-hard"のクラスは「Cと同じ程度かそれ以上に難しい」ということを意味するが、実際には「還元 (reduction)」によって定義される。 還元にも種類があり、"xx-hard"のクラスごとに定義が違うことがあるので注意する必要がある。 基本的には、「Aが解けたらBが(相対的に)効率的に解ける」ということを「BをAに還元した」と言う。
クラスCに対する"C-complete"のクラスは「CかつC-hard」として定義される。