本研究では, 以下のような場合を扱う. 商店などで各顧客が同時に購入する品物を トランザクションと呼ばれる集合で表す. データベースはトランザクションの多重集合である. このようなデータベースから データマイニングで求めたい情報の一つとして, 頻出集合がある. 集合Xが頻出集合であるとは, データベースD, および最小サポート数と呼ばれる整数sに対して, D中のトランザクションうち$ X$を包含するものがs個以上存在すること をいう. これまでにデータベースから頻出集合を全て求める手法は いくか提案されているが, それに必要な計算量については, あまり議論されていない.
データベースD, 正整数s, kが与えられたとき, 要素数k以上の 頻出集合が存在するかどうかを判定する問題を頻出集合問題と呼ぶ. 本研究では, データマイニングの基本的な問題である 頻出集合問題がNP完全 であることを示した. また関連する問題である, 高共起度集合問題及び最大集合積問題がNP完全であることを示した.