要素の明確性の問題

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

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

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

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

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

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

量子アルゴリズムはクエリでこの問題をより速く解くことができます。最適なアルゴリズムはAndris Ambainisによるものです。^[7] Yaoyun Shiは、範囲のサイズが十分に大きい場合の厳しい下限を初めて証明しました。^[8] Ambainis ^[9]とKutin ^[10]は独立して（そして異なる証明を介して）彼の研究を拡張し、すべての関数の下限を取得しました。 ${\textstyle \Theta (n^{2/3})}$

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

• 衝突問題