Loading article…
計算複雑性理論では、スパース言語とは、言語内の長さnの文字列の数を数える複雑性関数がnの多項式関数で制限されるような形式言語(文字列の集合)です。これらは主に、複雑性クラスNPと他のクラスの関係の研究に使用されます。すべてのスパース言語の複雑性クラスはSPARSEと呼ばれます。
疎な言語は、長さnの文字列が合計 2 n個あるため疎と呼ばれます。言語にこのような文字列が多項式の数だけ含まれる場合、長さnの文字列の割合はn が大きくなるにつれて急速にゼロになります。すべての単項言語は疎です。非自明な疎な言語の例としては、ある固定されたkに対して正確にk 1 ビットを含むバイナリ文字列の集合が挙げられます。各nに対して、言語にはn kで制限される文字列のみが含まれます。
他の複雑性クラスとの関係
- SPARSE には、最大で任意の長さの文字列が 1 つだけある単項言語のクラスであるTALLY が含まれます。
- P /polyの言語はすべてスパース言語というわけではないが、 P /polyの任意の言語からスパース言語への多項式時間チューリング還元が存在する。 [1]
- フォーチュンは 1979 年に、任意のスパース言語が共 NP完全であればP = NPであることを示した。[2]マハニーはこれを用いて 1982 年に、任意のスパース言語がNP完全であればP = NPであることを示した（これがマハニーの定理である）。[3]左集合に基づくこの証明は、1991 年に荻原と渡辺によってより簡単な証明が行われた。[4]マハニーの議論では、実際にはスパース言語が NP に属することを要求していない（NP 困難なスパース集合が存在するということは、NP 完全なスパース集合が存在することを意味するため）。そのため、P = NPの場合にのみ、スパースNP困難集合が存在する。[5]
- さらに、NPにPに存在しないスパース言語が存在する場合にのみ、E ≠ NEとなる。[6]
- NP完全言語からスパース言語へのチューリング還元（マハニーの定理からのカープ還元とは対照的）が存在するのは、次の場合のみです。
- 1999年、Jin-Yi CaiとD. Sivakumarは、Ogiharaの研究を基に、疎なP完全問題が存在する場合、L = Pであることを示した。[7]
参考文献
- ^ Jin-Yi Cai. 講義 11: P=poly、スパース セット、および Mahaney の定理。CS 810: 複雑性理論入門。ウィスコンシン大学マディソン校。2003 年 9 月 18 日 (PDF)
- ^ S. Fortune. スパース完全集合に関する注記。SIAM Journal on Computing、第8巻、第3号、pp.431–433。1979年。
- ^ SR Mahaney. NPのスパース完全集合：BermanとHartmanisの予想の解決。Journal of Computer and System Sciences 25:130–143。1982年。
- ^ M. Ogiwara および O. Watanabe. NP 集合からスパース集合への多項式時間有界真理値表還元可能性について。SIAM Journal on Computing巻 20、pp.471–483。1991 年。
- ^ バルカサル、ホセ・ルイス;ディアス、ジョセップ。ガバロ、ホアキン (1990)。構造の複雑性 II．スプリンガー。 130–131ページ。ISBN 3-540-52079-1。
- ^ Juris Hartmanis、Neil Immerman、Vivian Sewelson。NP-P におけるスパース セット: EXPTIME と NEXPTIME。Information and Control、第 65 巻、第 2/3 号、pp.158–181。1985 年。ACM デジタル ライブラリ
- ^ Jin-Yi Cai および D. Sivakumar。P のスパースハードセット: Hartmanis 予想の解決。Journal of Computer and System Sciences、第 58 巻、第 2 号、pp.280–296。1999 年。ISSN 0022-0000。Citeseer で
外部リンク
- ランス・フォートナウ。お気に入りの定理: 小さな集合。2006 年 4 月 18 日。
- ウィリアム・ガサーチ. スパースセット（マハニーへのトリビュート）. 2007 年 6 月 29 日.
- 複雑性動物園: SPARSE