Planted clique とは

計算複雑性理論では、無向グラフの植えられたクリークまたは隠れクリークは、頂点のサブセットを選択し、そのサブセット内の頂点の各対の間にエッジを追加することによって、別のグラフから形成されたクリークである。植え付けられたクリークの問題は、植えられたクリークを持つグラフからランダムなグラフを区別するアルゴリズムの問​​題です。これはクリークの問題のバリエーションです。擬似多項式時間で解くことができるが、クリークサイズの中間値については多項式時間で解くことができないと推測される。多項式時間解が存在しないという推測は、植え付けられたクリーク推測と呼ばれ、計算硬度の仮定として使用されています。