要素の明確性の問題

計算複雑性理論において、要素の区別の問題または要素の一意性の問題は、リストのすべての要素が異なるかどうかを判断する問題です。

これは、様々な計算モデルにおいてよく研究されている問題です。この問題は、リストをソートし、連続する等しい要素があるかどうかを確認することで解決できます。また、各項目をハッシュテーブルに挿入し、同じハッシュテーブルセルに配置された要素のみを比較するランダム化アルゴリズムによって、線形期待時間で解決できる場合もあります。^[1]

要素の区別の問題を問題自体に還元することによって、つまり、問題の問題を解決した後で要素の一意性の問題の解決策をすぐに見つけることができることを実証することによって、計算の複雑さのいくつかの下限が証明されます。

決定木の複雑さ

決定木や代数決定木などの比較ベースの計算モデルにおいて、サイズの問題を解決するために必要な比較回数はです。ここで、はビッグシータ表記法を呼び出します。これは、問題が（線形関数）に比例する比較回数で解決でき、すべての解にはこれだけの比較が必要であることを意味します。^[2]これらの計算モデルでは、入力数値は（ハッシュテーブルソリューションのように）コンピュータのメモリのインデックスとして使用することはできませんが、その値の単純な代数関数を計算して比較することによってのみアクセスできます。これらのモデルでは、比較ソートに基づくアルゴリズムは、可能な限り最良の比較回数の定数倍で問題を解決します。同じ下限が、ランダム化代数決定木モデルにおける期待される比較回数にも適用されます。^[3]^[4] $n$ $\Theta (n\log n)$ $\Theta$ $n\log n$

実RAMの複雑度

問題の要素が実数である場合、決定木の下限は、実数の加算、減算、乗算、比較、および除算または剰余（「床」）を含む命令セットを持つ実ランダムアクセスマシンモデルに拡張されます。 ^[5]したがって、このモデルにおける問題の複雑さもとなります。このRAMモデルは、テーブルへのインデックス付けを使用するアルゴリズムを包含しているため、代数的決定木モデルよりも多くのアルゴリズムをカバーしています。ただし、このモデルでは、決定だけでなく、すべてのプログラムステップがカウントされます $\Theta (n\log n)$

チューリングマシンの計算量

単一テープ決定性チューリングマシンは、各 $m$ $\geq log$ $n$ ビットのn要素に対して、 $O$ $($ $n$ $2$ $m$ $($ $m$ $+ 2 - log$ $n$ $))$ の時間で問題を解くことができますが、非決定性マシンでは、時間計算量は $O$ $($ $nm$ $($ $n$ $+ log$ $m$ $))$ です。^[6]

量子計算量

量子アルゴリズムは、クエリでこの問題をより速く解くことができます。最適なアルゴリズムは、アンドリス・アンバイニスによるものです。^[7]ヤオユン・シーは、範囲のサイズが十分に大きい場合のタイトな下限を初めて証明しました。^[8]アンバイニス^[9]とクティン^[10]は独立して（そして異なる証明によって）、すべての関数の下限を得るために彼の研究を拡張しました ${\textstyle \Theta (n^{2/3})}$

一般化: 繰り返し要素を見つける

サイズの多重集合において、回以上出現する要素は、比較に基づくアルゴリズムであるミスラ・グリース・ヘビーヒッターアルゴリズムによって、時間で発見される可能性があります。要素の個別性問題は、この問題の特殊なケースであり、となります。この時間は、決定木計算モデルの下では最適です。 ^[11] $n/k$ $n$ $O(n\log k)$ $k=n$

参照

衝突問題

参考文献

^ Gil, J.; Meyer auf der Heide, F.; Wigderson, A. (1990)、「すべてのキーを定数時間でハッシュできるわけではない」、Proc. 22nd ACM Symposium on Theory of Computing、pp. 244– 253、doi : 10.1145/100216.100247、S2CID 11943779。
^ ベン＝オール、マイケル（1983）、「代数計算木の下限値」、第15回ACM計算理論シンポジウム論文集、pp.80-86 、doi : 10.1145 /800061.808735。
^ ディマ、グリゴリエフ; Karpinski, マレク;ハイデ、フリードヘルム・マイヤー。 Smolensky、Roman (1996)、「ランダム化代数決定木の下限」、Computational Complexity、6 (4): 357、doi :10.1007/BF01270387、S2CID 1462184 。
^ Grigoriev, Dima (1999)、「ゼロ特性体上のランダム計算木の計算複雑度の下限」、計算複雑性、8 (4): 316– 329、doi :10.1007/s000370050002、S2CID 10641238 。
^ ベン・アムラム、アミール・M.;ガリル、ズヴィ（2001）、「代数ランダムアクセスマシンの位相的下限値」、SIAM Journal on Computing、31（3）：722–761、doi：10.1137/S0097539797329397。
^ Ben-Amram, Amir M.; Berkman, Omer; Petersen, Holger (2003)、「1テープチューリングマシンにおける要素の区別：完全な解」、Acta Informatica、40 (2): 81– 94、doi :10.1007/s00236-003-0125-8、S2CID 24821585
^ Ambainis, Andris (2007)、「要素の識別性のための量子ウォークアルゴリズム」、SIAM Journal on Computing、37 (1): 210– 239、arXiv : quant-ph/0311001、doi :10.1137/S0097539705447311
^ Shi, Y. (2002).衝突問題と要素の区別問題における量子下限値. 第43回コンピュータサイエンス基礎シンポジウム論文集. pp. 513– 519. arXiv : quant-ph/0112086 . doi :10.1109/SFCS.2002.1181975.
^ Ambainis, A. (2005). 「量子計算量における多項式次数と下限値：小範囲における衝突と要素の区別」.計算理論. 1 (1): 37– 46. doi : 10.4086/toc.2005.v001a003 .
^ Kutin, S. (2005). 「小範囲衝突問題に対する量子下界」.計算理論. 1 (1): 29– 36. doi : 10.4086/toc.2005.v001a002 .
^ Misra, J.; Gries, D. (1982)、「繰り返し要素の検索」、コンピュータプログラミング科学、2 (2): 143– 152、doi :10.1016/0167-6423(82)90012-0、hdl : 1813/6345 。

[1] Gil, J.; Meyer auf der Heide, F.; Wigderson, A. (1990)、「すべてのキーを定数時間でハッシュできるわけではない」、Proc. 22nd ACM Symposium on Theory of Computing、pp. 244– 253、doi : 10.1145/100216.100247、S2CID 11943779。

[2] ベン＝オール、マイケル（1983）、「代数計算木の下限値」、第15回ACM計算理論シンポジウム論文集、pp.80-86 、doi : 10.1145 /800061.808735。

[3] ディマ、グリゴリエフ; Karpinski, マレク;ハイデ、フリードヘルム・マイヤー。 Smolensky、Roman (1996)、「ランダム化代数決定木の下限」、Computational Complexity、6 (4): 357、doi :10.1007/BF01270387、S2CID 1462184 。

[4] Grigoriev, Dima (1999)、「ゼロ特性体上のランダム計算木の計算複雑度の下限」、計算複雑性、8 (4): 316– 329、doi :10.1007/s000370050002、S2CID 10641238 。

[5] ベン・アムラム、アミール・M.;ガリル、ズヴィ（2001）、「代数ランダムアクセスマシンの位相的下限値」、SIAM Journal on Computing、31（3）：722–761、doi：10.1137/S0097539797329397。

[6] Ben-Amram, Amir M.; Berkman, Omer; Petersen, Holger (2003)、「1テープチューリングマシンにおける要素の区別：完全な解」、Acta Informatica、40 (2): 81– 94、doi :10.1007/s00236-003-0125-8、S2CID 24821585

[7] Ambainis, Andris (2007)、「要素の識別性のための量子ウォークアルゴリズム」、SIAM Journal on Computing、37 (1): 210– 239、arXiv : quant-ph/0311001、doi :10.1137/S0097539705447311

[8] Shi, Y. (2002).衝突問題と要素の区別問題における量子下限値. 第43回コンピュータサイエンス基礎シンポジウム論文集. pp. 513– 519. arXiv : quant-ph/0112086 . doi :10.1109/SFCS.2002.1181975.

[9] Ambainis, A. (2005). 「量子計算量における多項式次数と下限値：小範囲における衝突と要素の区別」.計算理論. 1 (1): 37– 46. doi : 10.4086/toc.2005.v001a003 .

[10] Kutin, S. (2005). 「小範囲衝突問題に対する量子下界」.計算理論. 1 (1): 29– 36. doi : 10.4086/toc.2005.v001a002 .

[11] Misra, J.; Gries, D. (1982)、「繰り返し要素の検索」、コンピュータプログラミング科学、2 (2): 143– 152、doi :10.1016/0167-6423(82)90012-0、hdl : 1813/6345 。