スパム対策の一環として, 電子メールを一通送信する毎に, メール送信ユーザにコストを支払わせ てメールの大量送信を抑制する手法が研究されている. ここでいうコストとは計算資源 (時間, 計算パワー)のことであり, 実際にはプライシング関数と呼ばれる関数の計算を 課すことになる. これにより単位時間当りに送信可能な電子メールの数を制限すること ができ, スパムが抑制されることが期待できる. しかしながら適当なプライシング関数 はいまだ提案されておらず, その構成法が重要な問題点となっている.
本発表では, 始めにスパムメールの現状を報告し, 続いてプライシング手法の既存研究 を紹介する. さらにNP完全問題をプライシング関数に応用する提案手法を紹介し, その 利用法と問題点について述べる. また, NP完全問題の一つであるクリーク問題を用いた プライシング関数の構成法を提案する. 提案する構成法では平均計算量の下界に関する 既存研究の結果を利用しており, より公平で実用的なプライシング関数の実現になって いると考えられる.